Axe Complexités: Seminaire

Room B107, 12h.

The character table of the symmetric group $S_n$, of permutations of n objects, is of fundamental interest in theoretical physics, combinatorics as well as computational complexity theory. We investigate the implications of an identity, which has a geometrical interpretation in combinatorial topological field theories, relating the column sum of normalised central characters of $S_n$, to a sum of structure constants of multiplication in the centre of the group algebra of $S_n$. The identity leads to the proof that a combinatorial computation of the column sum belongs to complexity class #P. The sum of structure constants has an interpretation in terms of the counting of branched covers of the sphere. This allows the identification of a tractable subset of the structure constants related to genus zero covers. We use this subset to prove that the column sum for a conjugacy class labelled by partition λ is non-vanishing if and only if the permutations in the conjugacy class are even. This leads to the result that the determination of the vanishing or otherwise of the column sum is in complexity class P.

Room B107, 12h.

Among the many inequalities proved by Talagrand, the one which is most often labelled as Talagrand's inequality is the following: Let X_1... X_n be iid random variables in [0,1] and let f be a convex, 1-Lipschitz function from [0,1]^n to R. If M(f) stands for a median of f(X), then

P(|f(X) - Mf(X)|)>t < 4 exp (-t^2/4)

In particular, this inequality does not depend on n. We will see how this result compares with other concentration results and give some elements of the proof.

Video.

Room B107, 12h.

A triangulation of a convex polygon Σ is a set of pairwise non-crossing diagonals of Σ that decompose this polygon into triangles. The flip-graph F(Σ) of Σ is the graph whose vertices are these triangulations and whose edges connect two triangulations when they differ by a single diagonal. It turns out that F(Σ) can be represented alternatively using any Catalan family instead of triangulations and one can for example replace triangulation by binary trees and flips by rotations between them. This graph is the edge-graph of a polytope---the associahedron---and the complexity of computing distances between its vertices is a major open problem in computer science.

In a first part, this talk will focus on an elementary 2-approximation algorithm for flip distance computation and on a popular heuristics for this problem, based on the number of arcs crossings between two triangulations.

The second part focuses on the Sleator--Tarjan--Thurston 3-dimensional triangulation model for the paths in F(Σ). In their seminal 1988 article, they prove that, if the path is a geodesic, then this 3-dimensional model is a simplicial complex. The recent proof that this simplicial complex is flag is presented as well as several consequences as for instance, a proof that the arc crossings based flip distance estimation heuristics is, at best, a 3/2-approximation algorithm.

This talk is based on joint work with Zili Wang.

Video.

PhD defence of Alexandre Dupont-Bouillard.

Video ... Congratulations Alexandre!!

Because Σp2- and Σp3-hardness proofs are usually tedious and difficult, not so many complete problems for these classes are known. This is especially true in the areas of min-max regret robust optimization, network interdiction, most vital vertex problems, blocker problems, and two-stage adjustable robust optimization problems. Even though these areas are well-researched for over two decades and one would naturally expect many (if not most) of the problems occurring in these areas to be complete for the above classes, almost no completeness results exist in the literature. We address this lack of knowledge by introducing over 70 new Σp2-complete and Σp3-complete problems. We achieve this result by proving a new meta-theorem, which shows Σp2- and Σp3-completeness simultaneously for a huge class of problems. The majority of all earlier publications on Σp2- and Σp3-completeness in said areas are special cases of our meta-theorem. Our precise result is the following: We introduce a large list of problems for which the meta-theorem is applicable (including clique, vertex cover, knapsack, TSP, facility location and many more). For every problem on this list, we show: The interdiction/minimum cost blocker/most vital nodes problem (with element costs) is Σp2-complete. The min-max-regret problem with interval uncertainty is Σp2-complete. The two-stage adjustable robust optimization problem with discrete budgeted uncertainty is Σp3-complete. In summary, our work reveals the interesting insight that a large amount of NP-complete problems have the property that their min-max versions are 'automatically' Σp2-complete.

Readings:

• See the paper here.

Video.

We continue with the proof of the "switching lemma".

Readings:

• See these notes.

Video.

The fact that the PARITY function is not computable by bounded-depth polynomial-size families of Boolean circuits with unbounded fan-in is a fundamental result in circuit complexity, independently proved by Ajtai and by Furst, Saxe and Sipser in the 1980s.

I will give the basic definitions and an outline of the proof, which uses a powerful result called the "switching lemma". I will only prove the result using the switching lemma as a black box.

The proof of the switching lemma itself will be the topic of future talk.

Readings:

• Section 13.1 from here. In particular, we will go through Section 13.1.1 but NOT 13.1.2.

Video.

List of topics for the year 2024 discussed, together with possible working groups on specific topics.