Rohit Gurjar

most citedDerandomizing Isolation Lemma for

K_{3, 3}

-free and

K_{5}

-free Bipartite Graphs

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

collaborators

Showing cs.CCShow all

4 papers · 1 filter

cs.CC2023

Border Complexity of Symbolic Determinant under Rank One Restriction

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar +1

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_{0} + \sum_{i = 1}^{n} A_{i} x_{i}$ where the size of each $A_{i}$ is polynom…

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…

cs.CC2014

Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs

Rohit Gurjar, Arpita Korwar, Nitin Saxena +1

A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial ti…

cs.CC2014★ 1 cited

Hitting-sets for ROABP and Sum of Set-Multilinear circuits

Manindra Agrawal, Rohit Gurjar, Arpita Korwar +1

We give a $n^{O (l o g n)}$ -time ( $n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). Th…

Border Complexity of Symbolic Determinant under Rank One Restriction

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

Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs

Hitting-sets for ROABP and Sum of Set-Multilinear circuits

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