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

__
TR20-024
| 20th February 2020
__

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Randomized and Symmetric Catalytic Computation

__
TR19-095
| 18th July 2019
__

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Unambiguous Catalytic Computation

__
TR18-106
| 30th May 2018
__

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari#### Reachability in $O(\log n)$ Genus Graphs is in Unambiguous

Revisions: 1

__
TR18-004
| 3rd January 2018
__

Aayush Ojha, Raghunath Tewari#### Circuit Complexity of Bounded Planar Cutwidth Graph Matching

__
TR16-097
| 15th June 2016
__

Vivek Anand T Kallampally, Raghunath Tewari#### Trading Determinism for Time in Space Bounded Computations

__
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

__
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

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

__
TR11-060
| 15th April 2011
__

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

__
TR10-201
| 21st December 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari#### Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

__
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

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

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

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

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

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

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

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

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.

Aayush Ojha, Raghunath Tewari

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

Vivek Anand T Kallampally, Raghunath Tewari

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

Diptarka Chakraborty, Raghunath Tewari

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

Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

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

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

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

Samir Datta, Raghav Kulkarni, Raghunath Tewari

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

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