Ola Svensson: Small Extended Formulations via Monotone Circuits of Small Depth
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
Location: Patil/Kiva G449
Host: Ronitt Rubinfeld
Contact: Deborah Goodwin, 617.324.7303, firstname.lastname@example.org
Speaker URL: None
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
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.
Created by Deborah Goodwin at Thursday, December 08, 2016 at 7:14 AM.