BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Iterative algorithms and Sherali-Adams linear prog
ramming relaxations of graph isomorphism - Elitza
Maneva\, Universitat de Barcelona (UB)
DTSTART;TZID=Europe/London:20120203T140000
DTEND;TZID=Europe/London:20120203T150000
UID:TALK35733AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/35733
DESCRIPTION:The Weisfeiler-Lehman (WL) algorithm is an iterati
ve algorithm for certifying that two graphs are no
t isomorphic. At every iteration a label is genera
ted for each vertex based on the mutliset of label
s of its neighbors at the previous iteration. The
starting label is the degree of the vertex. When a
fixed point is reached the multisets of labels of
the vertices of the two graphs are compared. Thes
e are different only if the graphs are not isomorp
hic. In the k-level version of the WL algorithm a
label is instead generated for every k-tuple of ve
rtices. \n\nWe compare the WL algorithm to a hier
archy of linear programming relaxations of graph i
somorphism generated by the Sherali-Adams lift-and
-project method. It was already known that two gra
phs are fractionally isomorphic (i.e. there is a d
oubly stochastic matrix that converts one graph in
to the other) if and only if they are not distingu
ished by the first level of the WL algorithm. We s
how that\, furthermore\, the levels of the Sherali
-Adams hierarchy interleave in power with the high
er levels of the WL algorithm. \n\nJoint work wit
h Albert Atserias.
LOCATION:Room FW11\, Computer Laboratory\, William Gates Bu
ilding
CONTACT:Bjarki Holm
END:VEVENT
END:VCALENDAR