Evènement pour le groupe Algorithmique Distribuée


Date 2011-02-14  14:00-15:00
TitreAbout Lower Bounds on the Bit Complexity and the Execution Time of some Probabilistic Distributed Graph Algorithms  
RésuméWe present a general framework for proving lower bounds for the bit complexity (and thus the execution time) of some probabilistic distributed graph algorithms and we apply it to the complexity of some problems such as colouring, maximal matching or maximal independent set. We also give impossibility results on the existence of Las Vegas distributed algorithms to break symmetries at distance k for k >= 3. This is joint work with Y. Métivier, J.M. Robson and N. Saheb  
Lieus. 178 
OrateurAkka Zemmari 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index