Electrical Engineering and Computer Science

Theory Seminar

The Locality of Distributed Symmetry Breaking

Seth Pettie

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

Add to Google Calendar

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 http://web.eecs.umich.edu/~pettie/papers/Symmetry-Breaking.pdf.

Additional Information

Sponsor: EECS

Open to: Public