Benjamin Rossman: Formulas vs. circuits for small distance connectivity

Practicalities

Lunch is served at 12:00 noon (register at this doodle by Sunday June 15 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

Are poly-size boolean circuits strictly more powerful than poly-size boolean formulas? This question (also known as NC¹ vs. P) is one of the central open problems in complexity theory. We can also consider versions of this question for restricted classes of circuits. In the monotone setting, a super-polynomial separation of formulas vs. circuits was shown by Karchmer and Wigderson (1988). In recent work, we give the first super-polynomial separation in the (non-monotone) bounded-depth setting.

Our main result is a lower bound showing that depth-d formulas solving the Distance-k st-Connectivity problem require size n^log k for all k ≤ log log n and d ≤ log n/(log log n)^O(1). In contrast, this problem has circuits of size n^Ω(1) and depth O(log k) by the “recursive doubling” method of Savitch. As a corollary, it follows that depth-d circuits of size S cannot be simulated by depth-d formulas of size S^o(d) for all d ≤ log log log S (previously this was not known for any unbounded d → ∞).

The first part of the talk will be a gentle introduction to the question of formulas vs. circuits and the Distance-k st-Connectivity problem. After the break, I will give an overview of the new proof technique.