2 papers
cs.CC2026
An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
Deepanshu Kush
Since the breakthrough superpolynomial multilinear formula lower bounds of Raz (Theory of Computing 2006), proving such lower bounds against multilinear algebraic branching program…
cs.CC2025
Polynomial-Time PIT from (Almost) Necessary Assumptions
Robert Andrews, Deepanshu Kush, Roei Tell
The celebrated result of Kabanets and Impagliazzo (Computational Complexity, 2004) showed that PIT algorithms imply circuit lower bounds, and vice versa. Since then it has been a m…