Ben Rossman: Formulas vs. Circuits for Small Distance Connectivity

It is an elementary fact that every (unbounded fan-in) depth-d circuit of size S is equivalent to a depth-d formula of size at most S^d. Karchmer and Wigderson (1988) proved a converse to this fact in the *monotone* setting: a blow-up of S^Omega(d) is necessary to simulate monotone depth-d circuits by formulas for all S = n^O(1) and d = O(log n). In recent work, we give the first partial converse in the *boolean* setting: a blow-up of S^Omega(d) is necessary to simulate boolean depth-d circuits by formulas for all S = n^O(1) and d <= logloglog n. This result follows from a novel formula-size lower bound for the "Distance k Connectivity" problem (given a graph G of size n with specified vertices s and t, is there a path of length <= k from s to t?). Whereas this problem has polynomial-size boolean circuits of depth O(log k), we prove that solving Distance k Connectivity by boolean formulas of depth <= log n/polyloglog n requires size n^Omega(log k) for all k <= loglog n. The proof of this result introduces a new technique ("pathset complexity") which, for the first time, strongly distinguishes between formulas and circuits in the bounded-depth boolean setting. This talk will include an overview of the relevant background in circuit complexity.