Ben Rossman:New Separations of Formula vs. Circuit Size

Speaker: Ben Rossman , U. Toronto

Date: Thursday, March 30, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu

Reminder Subject: TALK: Ben Rossman:New Separations of Formula vs. Circuit Size

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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2016/2017.

Created by Rebecca Yadegar at Thursday, March 30, 2017 at 4:31 PM.