Theory Seminar

The Locality of Distributed Symmetry Breaking

Seth Pettie

Friday, January 18, 2013
10:30am - 11:30am
3941 BBB


About the Event

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

Additional Information

Event Sponsor: EECS

Open to: Public