9 citations · 13 across the 9 of their papers we have counts for
13 papers
Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
Archit Chauhan, Rohit Gurjar, Kilian Rothmund +1
The problem of recognizing (k, l)-tight graphs is a fundamental problem that has close connections to well studied problems like graph rigidity. The problem is better understood fo…
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 where the size of each is polynom…
On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
Rohit Gurjar, Nisheeth K. Vishnoi
We show that for any regular matroid on elements and any , the number of -minimum circuits, or circuits whose size is at most an -multiple of the minimum size of…
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…
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…
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 .
Bipartite Perfect Matching is in quasi-NC
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
We show that the bipartite perfect matching problem is in quasi-NC. That is, it has uniform circuits of quasi-polynomial size , and depth. Previousl…
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
Rohit Gurjar, Arpita Korwar, Nitin Saxena
We give improved hitting sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known order of the variables. T…
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…
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…
Hitting-sets for ROABP and Sum of Set-Multilinear circuits
Manindra Agrawal, Rohit Gurjar, Arpita Korwar +1
We give a -time ( is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). Th…
Hitting-sets for low-distance multilinear depth-3
Manindra Agrawal, Rohit Gurjar, Arpita Korwar +1
The depth- model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known…
Fixed-Parameter Extrapolation and Aperiodic Order
Stephen Fenner, Frederic Green, Steven Homer
Fix any . We say that a set is - if, whenever and are in , the point is also in . If is also (topolo…