Raghunath Tewari

most citedDerandomizing Isolation Lemma for

K_{3, 3}

-free and

K_{5}

-free Bipartite Graphs

1 citations · 1 across the 2 of their papers we have counts for

collaborators

3 papers

cs.CC2024★ 1 cited

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…

cs.DS2015

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

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

cs.CC2014★ 1 cited

Derandomizing Isolation Lemma for $K_{3, 3}$ -free and $K_{5}$ -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…

Lossy Catalytic Computation

An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Derandomizing Isolation Lemma for K3,3​-free and K5​-free Bipartite Graphs

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

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