Correlation decay in randomized local algorithms on regular graphs

Type: 
PhD Student Seminar
Audience: 
Open to the Public
Building: 
Zrinyi u. 14
Room: 
310/A
Wednesday, November 27, 2013 - 2:00pm
Add to Calendar
Date: 
Wednesday, November 27, 2013 - 2:00pm to 4:00pm

Abstract: We examine randomized local algorithms on regular graphs that do not contain short cycles. First we assign independent and identically distributed random variables to the vertices of the graph; this is a random labelling. Then every vertex gets a new random variable, depending on its labelled neighbourhood; the rule of this decision is deterministic and it is the same for all vertices. In the talk we present an upper bound on the correlation of the latter random variables belonging to vertices at a given distance. This bound decays exponentially fast as a function of the distance. This is joint work with Balazs Szegedy and Balint Virag.

You can watch the lecture here: 

http://www.youtube.com/watch?v=6QPis6fS6Fk&list=PL_0phSnA7tyQJDn-5hacAuE...