Formulas versus Circuits
Boolean circuits (acyclic networks of AND, OR, NOT gates) are a simple abstract model of computer hardware. Boolean formulas (circuits with the structure of a tree) are an even simpler “memoryless” model, in which the result of each subcomputation is used only once. Despite this apparent limitation, it is unknown whether formulas are strictly less powerful than circuits of comparable size. This fundamental question of formulas vs circuits (formally whether NC1 equals P/poly) is one of the biggest open problems in complexity theory.
In this talk, I will discuss two lines of my work on this question. One line separates the power of bounded-depth formulas vs circuits by sharpening some classic tools, including the switching lemma and polynomial approximation method. The other line gives lower bounds for the H-subgraph isomorphism problem, the task of determining whether a given graph contains a copy of a fixed pattern H. These results tie the circuit and formula size of H-subgraph isomorphism to natural invariants of the pattern H (treewidth and treedepth), with implications that answer longstanding questions in circuit complexity and finite model theory. Looking forward, I will explain why the k-cycle problem in the random graph G(n,p) is a promising candidate for an eventual separation of unrestricted formulas vs circuits.
Benjamin Rossman is an assistant professor of mathematics and computer science at the University of Toronto. His research centers on computational complexity and logic. He obtained his PhD from MIT where his dissertation on the average-case complexity of the clique problem received the George M. Sprowls Award. Before joining Toronto, he was a researcher at the National Institute of Informatics in Tokyo, Japan and a postdoctoral fellow at the Tokyo Institute of Technology and the Simons Institute for the Theory of Computing. He was an invited speaker at the 2018 International Congress of Mathematicians, and he is a recipient of a Sloan Research Fellowship, the André Aisenstadt Prize in Mathematics, and best paper awards at FOCS, CCC and LICS.