Evènement pour le groupe
Algorithmique Distribuée
Date | 2011-02-14 14:00-15:00 |
Titre | About 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
|
Lieu | s. 178 |
Orateur | Akka Zemmari |
Url | LaBRI |
Aucun document lié à cet événement.
RetourRetour à l'index