Vendredi 15 Juin

Retour à la vue des calendrier
Vendredi 15 Juin
Heure: 10:30 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
Description: Joanna Ochremiak The isomorphisms between two graphs can be described by the solutions of a system of polynomial inequalities and equations. We analyse the relative power of different proof systems which can be used to certify that a system corresponding to a pair of non-isomorphic graphs has no solution. Our results complete a full cycle of implications to show that, for the graph isomorphism problem, the Sherali-Adams, Polynomial Calculus and Sums-of-Squares proof systems are equally powerful, up to a constant loss in the degree. We prove this statement purely about the relative strength of proof systems through an excursion into the descriptive complexity of the ellipsoid method and bounded-variable infinitary logics. This is joint work with Albert Atserias.