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…