New separations of formula vs. circuit size
, U. Toronto
Date: Wednesday, April 12, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT
Contact: Rebecca Yadegar, firstname.lastname@example.org
Speaker URL: None
TALK: TODAY Ben Rossman: New separations of formula vs. circuit size
Abstract: 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.
Created by Rebecca Yadegar at Wednesday, April 12, 2017 at 11:18 AM.