Ola Svensson: Small Extended Formulations via Monotone Circuits of Small Depth

Speaker: Ola Svensson, EPFL

Date: Tuesday, December 13, 2016

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

Refreshments: 3:45 PM

Public: Yes

Location: Patil/Kiva G449

Event Type:

Room Description:

Host: Ronitt Rubinfeld

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Ola Svensson: Small Extended Formulations via Monotone Circuits of Small Depth

Abstract: Extended formulations have received considerable amount of attention recently,
mostly for proving impossibility results. These are results of the following
type: in order to solve problem A, you need a linear/semidefinite program of
large (super polynomial) size.

In this talk, we complement these impossibility results using a connection to
circuit complexity via Karchmer-Wigderson games. Specifically, we use small
depth circuits to show that covering integer programs can be approximated by
linear programs of quasi-polynomial size. Previously, relaxations of
comparable strength required exponential size and were obtained by so-called
knapsack-cover inequalities that have found widespread use in combinatorial
optimization.

Finally, we mention some other known intriguing consequences of the mentioned
connection between extended formulations and circuit complexity. In particular,
it immediately relates two celebrated results: Rothvoss' exponential lower
bound on the extension complexity of the perfect matching polytope implies
Raz-Wigderson's linear lower bound for the monotone circuit depth of the
perfect matching function.

Acknowledgments: This is based on joint work with Abbas Bazzi, Samuel Fiorini,
and Sangxia Huang. The connection between the size of the matching polytope and
the depth of monotone circuits was pointed out by Mika Göös.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) Seminar Series 2016.

Created by Deborah Goodwin Email at Thursday, December 08, 2016 at 7:14 AM.