Prochains exposés
SPOT 104 - Lundi 9 mars 2026 – Salle des thèses (C002) à l’ENSEEIHT (N7), 2 rue Charles Camichel, 31000 Toulouse
14h – Thorsten Theobald (Institut für Mathematik, Goethe-Universität, Frankfurt am Main) – A stable-set bound and maximal numbers of Nash equilibria in bimatrix games
Quint and Shubik (1997) conjectured that a non-degenerate $n \times n$ game has at most $2^n-1$ Nash equilibria in mixed strategies. The conjecture is true for $n \le 4$ but false for $n \ge 6$. We answer it positively for the remaining case $n=5$, which had been open since 1999. The problem can be translated to a combinatorial question about the vertices of a pair of simple $n$-polytopes with $2n$ facets. We introduce a novel obstruction based on the index of an equilibrium, which states that equilibrium vertices belong to two equal-sized disjoint stable sets of the graph of the polytope. This bound is verified directly using the known classification of the 159,375 combinatorial types of dual neighborly polytopes in dimension 5 with 10 facets. Non-neighborly polytopes are analyzed with additional combinatorial techniques where the bound is used for their disjoint facets.
Joint work with Constantin Ickstadt and Bernhard von Stengel.
15h – Nando Leijenhorst (LAAS-CNRS Toulouse) – Self-testing through exact SDP bounds
To show the difference between classical and quantum mechanics, one can use Bell inequalities. These are inequalities that are always satisfied in the classical model, but can be violated through quantum mechanics. Bounds on the maximum violation of a Bell inequality can be found through noncommutative polynomial optimization, in particular by using hermitian sums-of-squares polynomials and semidefinite programming (SDP).
Solvers return approximate solutions to an SDP, and in most cases only numerical upper and lower bounds on the violation are known. We propose to use the rounding method of arXiv:2403.16874 to find exact solutions to such SDPs. This allows us to show that CHSH mod 3, a generalization of the well-known Clauser–Horne–Shimony–Holt inequality, can be used for self-testing: there is, up to symmetries and unitary transformations, a unique set of operators and a unique state that maximize the violation.
In this talk, I will both explain the main ideas of the rounding method, and how the use of exact sum-of-squares certificates to prove that CHSH mod 3 can be used for self-testing.
Based on joint work with Igor Klep and Victor Magron, and on joint work with Henry Cohn and David de Laat (arXiv:2403.16874)
Comité local d’organisation
- Sonia Cafieri (ENAC)
- Frank Iutzeler (UPS et IMT)
- Victor Magron (LAAS-CNRS)
- Emmanuel Soubies (IRIT-CNRS)
- Edouard Pauwels (UT1 et TSE)
- Sixin Zhang (N7 et IRIT)
Cf un glossaire expliquant ces sigles et affiliations du système universitaire toulousain.
Fréquence et structure
Une séance par mois environ, avec deux conférenciers chaque fois (deux conférences de type différent : une orientée fondements et une orientée applications, un conférencier de l’environnement toulousain et un conférencier extérieur, un conférencier du milieu académique et un conférencier du milieu de l’industrie et des services, etc.).
Horaire habituel : le lundi après-midi de 14h à 16h.
Lieu
Sauf indication contraire, à la salle des thèses (C002) à l’ENSEEIHT (N7), 2 rue Charles Camichel, 31000 Toulouse (métro B, François Verdier). Attention, présentez-vous au poste de garde afin d’accéder au site.