Groupe de travail: Graphes, Algorithmes, Probabilités
Organized by Marc Lelarge. When? Thursday 14:00. Where? INRIA (Place d'Italie) 4th floor. Please send me an email if you want to attend/give a talk.
Dec 19: Marc, Arrow's Theorem a la Fourier.
Dec 12: Kumar, Influence Propagation in Social Networks.
Nov 28: Laurent V. Maximizing spread of influence through a social network (Kempe, Kleinberg, Tardos)
Mar 25: Laurent M. Approximating the cut-norm via Grothendieck's inequality, Siam J. Comput., N. Alon and A. Naor (2006)
Mar 11: Emilie Kaufmann, bayesian algorithms
Feb 18: Emilie Kaufmann, l'algorithme KL-UCB.
Feb 11: Mathieu, Multi-armed Bandit Allocation Indices.
Jan 28: Thibaut, Adversarial bandits Survey de Bubeck et Cesa-Bianchi
Dec 17: Thibaut, Bandits stochastiques Survey de Bubeck et Cesa-Bianchi
Nov 26: Laurent V. et Anne, Lovász local lemma.
Nov 19: Florence, Clustering data streams: Theory and practice by Guha, Meyerson, Mishra, Motwani, O'Callaghan, IEEE Trans. on KDE 2003.
Oct 29: Florence, Online facility location by Meyerson, FOCS 2001.
Oct 22: Alexandre, Maintaining stream statistics over sliding windows by Datar, Gionis, Indyk, Motwani, SIAM J. Comput. 2002.
Achlioptas, D. Database-friendlyrandomprojections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences, 2003.
Oct 15: Marc, Approximating the Frequency Moments and a Theorem of Johnson and Lindenstrauss.
Alon, N., Matias Y., Szegedy M. The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences, 1999
Indyk, P. Stable distributions, pseudorandom generators, embeddings, and data stream computation JACM 2006.
Dasgupta, S. and Gupta, A. An elementary proof of a theorem of Johnson and Lindenstrauss. RSA 2003.
Oct 8: Marc, Count-min sketch.
Cormode, G. and Muthukrishnan, S. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1): 58-75, 2005.
Oct 1: Marc, Introduction to data streams. Finding missing numbers, obtaining a uniform sample, Flajolet-Martin sketch.
Muthukrishnan, Data Streams: Algorithms and Applications. Chapter 1.
Lecture 3 of the course Algorithms for Modern Data Models. by Ashish Goel.
Lecture 4 of the course Fundamentals of Searching Web-scale Datasets. by Yufei Tao.