Abstract:
Understanding the relative power of circuits versus formulas (= tree-like circuits with fan-out 1) is a central challenge in complexity theory. It is widely believed that boolean circuits are strictly more powerful than boolean formulas of comparable size (i.e. NC1 is a proper subclass of P). Versions of this conjecture have been verified in a few restricted settings. Karchmer and Wigderson (1988) separated the power of *monotone* formulas vs. circuits via a lower bound for st-connectivity. In recent work, we obtained the first separation of formulas vs. circuits in the non-monotone *bounded-depth* setting. In this talk I will describe this result--which follows from a novel lower bound for small-distance st-connectivity--and discuss some future directions of research.