All reports by Author N. V. Vinodchandran:

__
TR21-043
| 15th March 2021
__

Peter Dixon, A. Pavan, N. V. Vinodchandran#### Promise Problems Meet Pseudodeterminism

__
TR19-091
| 7th July 2019
__

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe#### A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs

__
TR14-035
| 13th March 2014
__

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Yang#### New Time-Space Upperbounds for Directed Reachability in High-genus and $H$-minor-free Graphs.

__
TR14-008
| 20th January 2014
__

N. V. Vinodchandran#### Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.

__
TR11-060
| 15th April 2011
__

Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran#### ReachFewL = ReachUL

__
TR10-154
| 8th October 2010
__

Derrick Stolee, N. V. Vinodchandran#### Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs

__
TR10-151
| 30th September 2010
__

Raghunath Tewari, N. V. Vinodchandran#### Green’s Theorem and Isolation in Planar Graphs

__
TR10-079
| 28th April 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran#### Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

__
TR10-009
| 13th January 2010
__

A. Pavan, Raghunath Tewari, N. V. Vinodchandran#### On the Power of Unambiguity in Logspace

__
TR09-071
| 1st September 2009
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Kolmogorov Complexity in Randomness Extraction

__
TR09-049
| 5th May 2009
__

Derrick Stolee, Chris Bourke, N. V. Vinodchandran#### A log-space algorithm for reachability in planar DAGs with few sources

__
TR05-105
| 24th September 2005
__

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang#### Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

__
TR05-062
| 17th June 2005
__

A. Pavan, N. V. Vinodchandran#### 2-Local Random Reductions to 3-Valued Functions

__
TR04-056
| 1st July 2004
__

N. V. Vinodchandran#### A note on the circuit complexity of PP

__
TR04-053
| 17th June 2004
__

A. Pavan, N. V. Vinodchandran#### Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

__
TR04-025
| 24th January 2004
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Partial Bi-Immunity and NP-Completeness

__
TR98-078
| 1st December 1998
__

Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran#### The Query Complexity of Program Checking by Constant-Depth Circuits

Peter Dixon, A. Pavan, N. V. Vinodchandran

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high ... more >>>

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe

In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch ... more >>>

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Yang

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.

(1) A polynomial-time,

$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ...
more >>>

N. V. Vinodchandran

The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 ... more >>>

Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran

We show that two complexity classes introduced about two decades ago are equal. ReachUL is the class of problems decided by nondeterministic log-space machines which on every input have at most one computation path from the start configuration to any other configuration. ReachFewL, a natural generalization of ReachUL, is the ... more >>>

Derrick Stolee, N. V. Vinodchandran

We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let ${\cal G}(m,g)$ be the class of directed acyclic graphs with $m = m(n)$ source vertices embedded on a surface (orientable or non-orientable) of genus $g = g(n)$. We give a log-space reduction that ... more >>>

Raghunath Tewari, N. V. Vinodchandran

We show a simple application of Green’s theorem from multivariable calculus to the isolation problem in planar graphs. In particular, we construct a skew-symmetric, polynomially bounded, edge weight function for a directed planar graph in logspace such that the weight of any simple cycle in the graph is non-zero with ... more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran

We investigate the space complexity of certain perfect matching

problems over bipartite graphs embedded on surfaces of constant genus

(orientable or non-orientable). We show that the problems of deciding

whether such graphs have (1) a perfect matching or not and (2) a

unique perfect matching or not, are in the ...
more >>>

A. Pavan, Raghunath Tewari, N. V. Vinodchandran

We report progress on the \NL\ vs \UL\ problem.

\begin{itemize}

\item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$.

\item[-] We investigate the complexity of min-uniqueness - a central

notion in studying the \NL\ vs \UL\ problem.

more >>>

John Hitchcock, A. Pavan, N. V. Vinodchandran

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity

extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction

more >>>

Derrick Stolee, Chris Bourke, N. V. Vinodchandran

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang

We apply recent results on extracting randomness from independent

sources to ``extract'' Kolmogorov complexity. For any $\alpha,

\epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show

how to use a constant number of advice bits to efficiently

compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) >

(1-\epsilon)|y|$. ...
more >>>

A. Pavan, N. V. Vinodchandran

Yao (in a lecture at DIMACS Workshop on structural complexity and

cryptography) showed that if a language L is 2-locally-random

reducible to a Boolean functio, then L is in PSPACE/poly.

Fortnow and Szegedy quantitatively improved Yao's result to show that

such languages are in fact in NP/poly (Information Processing Letters, ...
more >>>

N. V. Vinodchandran

In this short note we show that for any integer k, there are

languages in the complexity class PP that do not have Boolean

circuits of size $n^k$.

A. Pavan, N. V. Vinodchandran

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine

and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes.

John Hitchcock, A. Pavan, N. V. Vinodchandran

The Turing and many-one completeness notions for $\NP$ have been

previously separated under {\em measure}, {\em genericity}, and {\em

bi-immunity} hypotheses on NP. The proofs of all these results rely

on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness ... more >>>

Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran

In this paper we study program checking (in the

sense of Blum and Kannan) using constant-depth circuits as

checkers. Our focus is on the number of queries made by the

checker to the program being checked and we term this as the

query complexity of the checker for the given ...
more >>>