3 papers
cs.DS2026
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…
cs.CC2026
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…
quant-ph2025
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…