Theory Seminar

The Locality of Distributed Symmetry Breaking

Seth PettieU-M

We present new methods for solving several classical symmetry breaking
tasks in distributed networks, such as finding maximal independent
sets, maximal matchings, and vertex-colorings.

This is joint work with Leonid Barenboim, Michael Elkin, and Johannes Schneider. An extended abstract appeared in FOCS 2012. PDF available at

Sponsored by