5 citations · 8 across the 10 of their papers we have counts for
14 papers · 1 filter
Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
Chetan Gupta, Raghunath Tewari, Vimal Raj Sharma
We show that given an embedding of an genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight pe…
Trading Determinism for Time: The k-Reach Problem
Ronak Bhadra, Raghunath Tewari
Kallampally and Tewari showed in 2016 that there can be a trade-off between determinism and time in space-bounded computations. This they did by describing an unambiguous non-deter…
Lossy Catalytic Computation
Chetan Gupta, Rahul Jain, Vimal Raj Sharma +1
A catalytic Turing machine is a variant of a Turing machine in which there exists an auxiliary tape in addition to the input tape and the work tape. This auxiliary tape is initiall…
Reachability and Matching in Single Crossing Minor Free Graphs
Samir Datta, Chetan Gupta, Rahul Jain +3
We show that for each single crossing graph , a polynomially bounded weight function for all -minor free graphs can be constructed in Logspace such that it gives nonzero…
Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
Chetan Gupta, Rahul Jain, Raghunath Tewari
A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an imp…
Two Player Hidden Pointer Chasing and Multi-Pass Lower Bounds in Turnstile Streams
Anay Mehrotra, Vibhor Porwal, Raghunath Tewari
The authors have withdrawn this paper due to an error in the proof of Lemma 3.4. -------------------------------------------------------------------------------------------- The au…
Reachability in High Treewidth Graphs
Rahul Jain, Raghunath Tewari
Reachability is the problem of deciding whether there is a path from one vertex to the other in the graph. Standard graph traversal algorithms such as DFS and BFS take linear time…
On Solving Reachability in Grid Digraphs using a Psuedoseparator
Rahul Jain, Raghunath Tewari
The reachability problem asks to decide if there exists a path from one vertex to another in a digraph. In a grid digraph, the vertices are the points of a two-dimensional square g…
Circuit Complexity of Bounded Planar Cutwidth Graph Matching
Aayush Ojha, Raghunath Tewari
Recently, perfect matching in bounded planar cutwidth bipartite graphs (\BGGM) was shown to be in ACC by Hansen et al.. They also conjectured that the problem is in AC. In…
Trading Determinism for Time in Space Bounded Computations
Vivek Anand T Kallampally, Raghunath Tewari
Savitch showed in that nondeterministic logspace (NL) is contained in deterministic space but his algorithm requires quasipolynomial time. The questi…
Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs
Diptarka Chakraborty, Raghunath Tewari
In this paper, we show that given a weighted, directed planar graph , and any , there exists a polynomial time and space algorithm that computes the…
Derandomizing Isolation Lemma for -free and -free Bipartite Graphs
Rahul Arora, Ashu Gupta, Rohit Gurjar +1
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…
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs
Samir Datta, Raghav Kulkarni, Raghunath Tewari +1
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 t…
On the Power of Unambiguity in Logspace
Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran
We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\Reach…