Talagrand's Inequality and Locality in Distributed Computing

Devdatt P. Dubhashi

October 1998

Abstract:

We illustrate the use of Talagrand's inequality and an extension of it to dependent random variables due to Marton for the analysis of distributed randomised algorithms, specifically, for edge colouring graphs

Available as PostScript, PDF, DVI.

 

Last modified: 2003-06-08 by webmaster.