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...