Fall 2018

Lower Bounds for Unrestricted Boolean Circuits: Open Problems

Monday, September 10th, 2018 4:00 pm4:30 pm

Add to Calendar


Sasha Kulikov (St. Petersburg Department of Steklov Institute of Mathematics)

To prove that P is not equal to NP, it suffices to prove a superpolynomial lower bound on Boolean circuit complexity of a function from NP. Currently, we are not even close to achieving this goal: we do not know how to prove a 4n lower bound. What is more depressing is that there are almost no techniques for proving circuit lower bounds. In this talk, we’ll briefly review various approaches that could potentially lead to stronger linear or superlinear lower bounds for unrestricted Boolean circuits (i.e., circuits with no restriction on depth, fan-out, or basis).