Ola Svensson: Small Extended Formulations via Monotone Circuits of Small Depth
Tuesday, December 13, 2016 - 4:00pm to 5:00pm
Refreshments:
Light Refreshments at 3:50pm
Location:
Patil/Kiva G449
Speaker:
Ola Svensson, EPFL
Seminar group:
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.