Monday, January 16, 2017
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Room: MA 041
Lecture - 14:15
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.
Colloquium - 16:00
Abstract:
Random graphs have been studied intensively since the late 50s. In particular, the binomial random graph G(n,p) has been considered where every pair among n vertices is independently adjacent with probability p. Already in one of the first papers on random graphs, Erdős and Renyi describe the emergence of a unique giant component (that is, it contains a constant fraction of the vertices) if p becomes larger than 1/n.
The binomial random graph is very homogeneous. In contrast to this, Molloy and Reed (1995) considered graphs chosen uniformly at random from the set of all graphs with a given degree sequence D=(d_1,... , d_n). They observe a similar behaviour as in the G(n,p) model and characterized all degree sequences for which almost all graphs with this degree sequence have a giant component, provided several strong technical conditions hold. These conditions have been relaxed by many others. We prove a simple characterization for all degree sequences. This also shows that the heuristic argument used by Molloy and Reed is not true for all degree sequences.
This is joint work with Guillem Perarnau, Dieter Rautenbach, and Bruce Reed.