Speaker: Benjamin Rossman, National Institute of Informatics, Tokyo
Title: Formulas vs. Circuits for Small Distance Connectivity
In this talk, I will present a recent result which gives the first super-polynomial separation in the power of bounded-depth (unbounded fan-in) boolean formulas vs. circuits. Consider the elementary fact that every depth-d circuit of size S is equivalent to a depth-d formula of size at most S^d. We prove that a blow-up of S^Ω(d) is necessary for all d <= logloglog S; previously no lower bound better than S^Ω(1) was known for any super-constant d. This result follows from a novel formula size lower bound for the problem of Distance-k st-Connectivity. As a further corollary, we obtain a tight Ω(log k) lower bound on the depth of polynomial-size circuits solving Distance-k st Connectivity for all k <= loglog n. This improves the previous Ω(loglog k) lower bound of Beame, Impagliazzo, Pitassi (1998) and matches the O(log k) upper bound from Savitch's algorithm.