Theory Seminar
The Locality of Distributed Symmetry Breaking
Seth PettieU-M
WHEN:
Friday, January 18, 2013 @ 10:30 am
Add to Google Calendar
Add to Google Calendar
SHARE:
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 http://web.eecs.umich.edu/~pettie/papers/Symmetry-Breaking.pdf.