9 citations · 16 across the 7 of their papers we have counts for
10 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…
Tight bounds on depth-2 QAC-circuits computing parity
Stephen Fenner, Daniel Grier, Daniel Padé +1
We show that the parity of more than three non-target input bits cannot be computed by QAC-circuits of depth-2, not even uncleanly, regardless of the number of ancilla qubits. This…
Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
Pranjal Dutta, Amit Sinhababu, Thomas Thierauf
For a polynomial from a class of polynomials, we show that the problem to compute all the constant degree irreducible factors of reduces in polynomial time to…
Depth-2 QAC circuits cannot simulate quantum parity
Daniel Padé, Stephen Fenner, Daniel Grier +1
We show that the quantum parity gate on qubits cannot be cleanly simulated by a quantum circuit with two layers of arbitrary C-SIGN gates of any arity and arbitrary 1-qubit…
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…
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…