moteur de recherche

Séminaire Algo - Joanna Ochremiak
Séminaire Algo - Joanna Ochremiak
27-mars-2018 14:30
Il y a: 57 days

Joanna Ochremiak

Sum-of-Squares, Counting Logics and Graph Isomorphism

Bâtiment Lavoisier, salle LAV108

Abstract: The isomorphisms between two graphs can be described by the integral solutions of a system of linear equations and inequalities. We show that the Lasserre hierarchy of increasingly tighter semidefinite relaxations of this integer linear program is closely related to the well-known colour-refinement heuristic for graph isomorphism called the Weisfeiler-Lehman algorithm, or equivalently, to indistinguishability in logics with counting quantifiers and a bounded number of variables. This is joint work with Albert Atserias.

<- retour: