activity
20122026
most citedIdentity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs

9 citations · 13 across the 9 of their papers we have counts for

collaborators
Showing 2017Show all

3 papers · 1 filter

cs.CC2017

Pseudorandom Bits for Oblivious Branching Programs

Rohit Gurjar, Ben Lee Volk

We construct a pseudorandom generator which fools read- oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequen…

cs.DS2017

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi

We present a geometric approach towards derandomizing the Isolation Lemma by Mulmuley, Vazirani, and Vazirani. In particular, our approach produces a quasi-polynomial family of wei…

cs.DM2017★ 1 cited

Extended Formulations for Polytopes of Regular Matroids

Rohit Gurjar, Nisheeth K. Vishnoi

We present a simple proof of the fact that the base (and independence) polytope of a rank regular matroid over elements has an extension complexity .