Vendredi 15 Juin
Heure: 
10:30  12:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Definable Ellipsoid Method, SumsofSquares 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 nonisomorphic graphs has no solution. Our results complete a full cycle of implications to show that, for the graph isomorphism problem, the SheraliAdams, Polynomial Calculus and SumsofSquares 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 boundedvariable infinitary logics. This is joint work with Albert Atserias. 

