Articles proposés dans le cadre du cours M2R Modèles de calcul, Complexité, Approximation et Heuristiques de l'Université de Grenoble.

Articles proposés cette année sur la partie: Modèle probabiliste: Algorithmes et Complexité

• Rajeev Motwani, Prabhakar Raghavan. Randomized Algorithms - Chap 9: Geometric Algorithms and Linear Programming. pp 234-277. Cambrdige University Press, 2000.
• Rajeev Motwani, Prabhakar Raghavan. Randomized Algorithms - Chap 10: Graph Algorithms. pp 278-305. Cambrdige University Press, 2000.
• R. Cole, U. Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. [ local ] Proceedings of the eighteenth annual ACM symposium on Theory of computing, STOC '86, pp 206--219,
  • Abstract: [...] This paper introduces a new deterministic coin tossing technique that provides for a fast and efficient breaking of a symmetric situation in parallel. Previously, it was known how to break such symmetries only by means of randomization. Interestingly, the structure of all the algorithms in this paper follow a paradigm which we call accelerating cascades. Given several alternative parallel algorithms for the same problem, this paradigm constructs a new algorithm for the same problem out of these algorithms; the performance of the new algorithm compares favourably with that of any of its building blocks.
• [assez difficile] Jeff Abrahamson, Béla Csaba, Ali Shokoufandeh: Optimal Random Matchings on Trees and Applications. Random 2008, pp 254-265 [ local ]
  • Abstract. In this paper we will consider tight upper and lower bounds on the weight of the optimal matching for random point sets distributed among the leaves of a tree, as a function of its cardinality. Specifically, given two n sets of points R = {r1,...,rn} and B = {b1,...,bn} dis- tributed uniformly and randomly on the m leaves of λ-Hierarchically Separated Trees with branching factor b such that each of its leaves is at depth δ, we will prove that the expected weight of optimal matching between R and B is Θ(√nb h (√bλ)k ), for h = min(δ, log n). Using a k=1 b simple embedding algorithm from Rd to HSTs, we are able to reproduce the results concerning the expected optimal transportation cost in [0, 1]d , except for d = 2. We also show that giving random weights to the points does not affect the expected matching weight by more than a constant factor. Finally, we prove upper bounds on several sets for which showing reasonable matching results would previously have been intractable, e.g., the Cantor set, and various fractals.
• [Assez difficile] Eric Allender, V Arvind and Fengming Wang. Uniform Derandomization from Pathetic Lower Bounds Random 2009.
  Question: random self-reducibility et application à la séparation entre TC0 (circuit booléens à fan-in et fan-out non borné et de profondeur constante) et NC1 (circuit booléens à fan-in borné et de profondeur logarithmique)
• [Difficile] Algorithmic Aspects of Property Testing in The Dense Graphs Model Oded Goldreich and Dana Ron. Random 2009.
• [Difficile] David P. Woodruff: Corruption and Recovery-Efficient Locally Decodable Codes. 584-595