2 papers
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…
cs.CC2017
Quantified Derandomization of Linear Threshold Circuits
Roei Tell
One of the prominent current challenges in complexity theory is the attempt to prove lower bounds for , the class of constant-depth, polynomial-size circuits with majority ga…