Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author N. V. Vinodchandran:

TR21-043 | 15th March 2021
Peter Dixon, A. Pavan, N. V. Vinodchandran

Promise Problems Meet Pseudodeterminism

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 >>>

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

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 >>>

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.

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 >>>

TR14-008 | 20th January 2014
N. V. Vinodchandran

Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.

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 >>>

TR11-060 | 15th April 2011
Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran

ReachFewL = ReachUL

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 >>>

TR10-154 | 8th October 2010
Derrick Stolee, N. V. Vinodchandran

Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs

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 >>>

TR10-151 | 30th September 2010
Raghunath Tewari, N. V. Vinodchandran

Green’s Theorem and Isolation in Planar Graphs

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 >>>

TR10-079 | 28th April 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran

Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

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 >>>

TR10-009 | 13th January 2010
A. Pavan, Raghunath Tewari, N. V. Vinodchandran

On the Power of Unambiguity in Logspace

We report progress on the \NL\ vs \UL\ problem.
\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 >>>

TR09-071 | 1st September 2009
John Hitchcock, A. Pavan, N. V. Vinodchandran

Kolmogorov Complexity in Randomness Extraction

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 >>>

TR09-049 | 5th May 2009
Derrick Stolee, Chris Bourke, N. V. Vinodchandran

A log-space algorithm for reachability in planar DAGs with few sources

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 >>>

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

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 >>>

TR05-062 | 17th June 2005
A. Pavan, N. V. Vinodchandran

2-Local Random Reductions to 3-Valued Functions

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 >>>

TR04-056 | 1st July 2004
N. V. Vinodchandran

A note on the circuit complexity of PP

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$.

more >>>

TR04-053 | 17th June 2004
A. Pavan, N. V. Vinodchandran

Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

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.

more >>>

TR04-025 | 24th January 2004
John Hitchcock, A. Pavan, N. V. Vinodchandran

Partial Bi-Immunity and NP-Completeness

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 >>>

TR98-078 | 1st December 1998
Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran

The Query Complexity of Program Checking by Constant-Depth Circuits

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 >>>

ISSN 1433-8092 | Imprint