Toward better formula lower bounds
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson · 2014
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P ⊈ NC1). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the first milestones toward proving super-polynomial circuit lower bounds.