New separations of formula vs. circuit size

Wednesday, April 12, 2017 - 4:00pm to 5:00pm
Ben Rossman
U. Toronto
 I will present some recent results on the power of formulas vs. circuits in the bounded-depth setting.  In joint work with Srikanth Srinivasan, we obtain a nearly optimal separation between the AC^0[⊕] formula vs. circuit size of the Approximate Majority function.  In other work, we show that the AC^0 circuit (resp. formula) size of the H-Subgraph Isomorphism problem is tied to the treewidth (resp. treedepth) of the pattern graph H.  The latter formula-size lower bound relies on a new “excluded-minor approximation” of treedepth (joint with Kenich Kawarabayashi).  The former is based on an improved construction of low-degree approximating polynomials for AC^0[⊕] formulas.