BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Iterative algorithms and Sherali-Adams linear programming relaxati
 ons of graph isomorphism - Elitza Maneva\, Universitat de Barcelona (UB)
DTSTART:20120203T140000Z
DTEND:20120203T150000Z
UID:TALK35733@talks.cam.ac.uk
CONTACT:Bjarki Holm
DESCRIPTION:The Weisfeiler-Lehman (WL) algorithm is an iterative algorithm
  for certifying that two graphs are not isomorphic. At every iteration a l
 abel is generated for each vertex based on the mutliset of labels of its n
 eighbors at the previous iteration. The starting label is the degree of th
 e vertex. When a fixed point is reached the multisets of labels of the ver
 tices of the two graphs are compared. These are different only if the grap
 hs are not isomorphic. In the k-level version of the WL algorithm a label 
 is instead generated for every k-tuple of vertices.  \n\nWe compare the WL
  algorithm to a hierarchy of linear programming relaxations of graph isomo
 rphism generated by the Sherali-Adams lift-and-project method. It was alre
 ady known that two graphs are fractionally isomorphic (i.e. there is a dou
 bly stochastic matrix that converts one graph into the other) if and only 
 if they are not distinguished by the first level of the WL algorithm. We s
 how that\, furthermore\, the levels of the Sherali-Adams hierarchy interle
 ave in power with the higher levels of the WL algorithm.  \n\nJoint work w
 ith Albert Atserias. 
LOCATION:Room FW11\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR