Department of Mathematics & Computer Science

Spraeker #1: Uli Wagner

Affiliation: ETH Zurich

 

Title: A Primer on Higher-Dimensional Expansion Properties

Abstract: Expansion properties of graphs are a well-studied topic in various branches of mathematics and computer science, and expanders - very sparse but highly connected graphs - have found numerous applications, e.g., in the design of networks, error-correcting codes, complexity theory, metric embeddings, and other areas.

Recently, higher-dimensional expansion properties of hypergraphs and simplicial complexes were introduced and studied by several independent groups of researchers coming from three different directions:

(1) Geometric measure theory and singularities (overlap properties) of maps from a simplicial complex to a manifold (Gromov)

(2) Higher-dimensional analogues of random graphs: random complexes and their connectivity properties (Linial and Meshulam)

(3) Higher-dimensional analogues of metric embeddings (Newman and Rabinovich)

In this talk, we aim to give a brief introduction to these higher-dimensional notions of expansion, focussing on the 2-dimensional case.

 

*********************************************************

 

Speaker #2: Samuel Fiorini

Affiliation: Université Libre de Bruxelles

 

Title: The complexity of polytopes

Abstract: I will survey recent work on a complexity measure for (convex) polytopes, called the extension complexity. The extension complexity of a polytope P is defined as the minimum number of facets of a polytope Q that projects to P. This measure is both natural, because it fits well with the applications of polytopes (especially, optimization), and elegant because it leads to beautiful results.

The extension complexity of a polytope P can be characterized both in terms of nonnegative factorizations (as studied in applied linear algebra) of related matrices known as slack matrices of P, and in terms of communication protocols (as studied in theoretical computer science) computing a slack matrix of P in expectation.

I will present the solution to a 20 years old problem due to Yannakakis about the extension complexity of the traveling salesman polytope, the polyhedral counterpart of the well-known traveling salesman problem. While it is still open whether the traveling salesman problem admits a polynomial time algorithm (because this is equivalent to the famous P versus NP problem), S. Massar (Brussels), S. Pokutta (Erlangen), H.R. Tiwary (Brussels), R. de Wolf (CWI) and myself could show that the extension complexity of the traveling salesman polytope is super-polynomial.

Time permitting, we will mention generalizations to semidefinite extensions, psd factorizations and quantum communication protocols, as well as open problems.