|
|
 |
|
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. |
|
|
