Please note: This seminar will take place in DC 1304 and online.
Deepanshu Kush, PhD student
Department of Computer Science, University of Toronto
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 major challenge to understand the precise connections between PIT and lower bounds. A main goal has been to understand which lower bounds suffice to obtain efficient PIT algorithms, and how close are they to lower bounds that are necessary for the conclusion.
We construct polynomial-time PIT algorithms from lower bounds that are, up to relatively minor remaining gaps, necessary for the existence of such algorithms. That is, we prove that these lower bounds are, up to the mentioned minor gaps, both sufficient and necessary for polynomial-time PIT.
The key to these improvements is studying PIT versus lower bounds in the uniform setting, in which we focus on proving lower bounds for uniform arithmetic circuits and their variants (and on deducing algorithms from such lower bounds). Indeed, by working in this setting we obtain results that are significantly tighter than previously known results concerning polynomial-time PIT vs lower bounds and are in fact also tighter than known hardness-vs-randomness connections in the Boolean setting.
This talk is based on joint work with Robert Andrews and Roei Tell.
To attend this seminar in person, please go to DC 1304. You can also .