Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Raghunath Tewari:

TR20-025 | 20th February 2020
Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists.

As a consequence, we obtain that deciding whether the ... more >>>

TR20-024 | 20th February 2020
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

Randomized and Symmetric Catalytic Computation

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

TR19-095 | 18th July 2019
Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

Unambiguous Catalytic Computation

The catalytic Turing machine is a model of computation defined by Buhrman, Cleve,
Kouck, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing
machine, this model has an extra space which is filled with arbitrary content in addition
to the clean space. In such a model we study ... more >>>

TR18-106 | 30th May 2018
Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

Reachability in $O(\log n)$ Genus Graphs is in Unambiguous

Revisions: 1

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices
$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous
logarithmic space.

more >>>

TR18-004 | 3rd January 2018
Aayush Ojha, Raghunath Tewari

Circuit Complexity of Bounded Planar Cutwidth Graph Matching

Recently, perfect matching in bounded planar cutwidth bipartite graphs
$BGGM$ was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that
the problem is in AC$^0$.
In this paper, we disprove their conjecture by showing that the problem is
not in AC$^0[p^{\alpha}]$ for every prime $p$. ... more >>>

TR16-097 | 15th June 2016
Vivek Anand T Kallampally, Raghunath Tewari

Trading Determinism for Time in Space Bounded Computations

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open.
... more >>>

TR15-016 | 16th January 2015
Diptarka Chakraborty, Raghunath Tewari

An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Revisions: 1

Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for ... more >>>

TR14-161 | 27th November 2014
Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs

Revisions: 2

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We ... 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 >>>

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-201 | 21st December 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari

Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in ... 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 >>>

ISSN 1433-8092 | Imprint