4 papers
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…
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…
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…