COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Iterative algorithms and Sherali-Adams linear programming relaxations of graph isomorphism

## Iterative algorithms and Sherali-Adams linear programming relaxations of graph isomorphismAdd to your list(s) Download to your calendar using vCal - Elitza Maneva, Universitat de Barcelona (UB)
- Friday 03 February 2012, 14:00-15:00
- Room FW11, Computer Laboratory, William Gates Building.
If you have a question about this talk, please contact Bjarki Holm. The Weisfeiler-Lehman (WL) algorithm is an iterative algorithm for certifying that two graphs are not isomorphic. At every iteration a label is generated for each vertex based on the mutliset of labels 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. These are different only if the graphs are not isomorphic. In the k-level version of the WL algorithm a label is instead generated for every k-tuple of vertices. We compare the WL algorithm to a hierarchy of linear programming relaxations of graph isomorphism generated by the Sherali-Adams lift-and-project method. It was already known that two graphs are fractionally isomorphic (i.e. there is a doubly 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 show that, furthermore, the levels of the Sherali-Adams hierarchy interleave in power with the higher levels of the WL algorithm. Joint work with Albert Atserias. This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Computer Laboratory talks
- Computing and Mathematics
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Room FW11, Computer Laboratory, William Gates Building
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsQualitative Research Forum - Open meetings Institution of Mechanical Engineers (Cambridgeshire Area) The Leverhulme Centre for Human Evolutionary Studies Seminars## Other talksIntelligent Self-Driving Vehicles The Intimate Relation between Mechanics and Geometry Designing Active Macroscopic Heat Engines The formation of high density dust rings and clumps: the role of vorticity Complement and microglia mediated sensory-motor synaptic loss in Spinal Muscular Atrophy Skyrmions, Quantum Graphs and Carbon-12 |