Resources on Sublinear Algorithms
Revision as of 11:41, 15 March 2016 by Krzysztof Onak (talk | contribs) (This should probably be replaced by a link to the book by Oded when it's ready.)
Contents
(Please add links only to class and workshop websites that provide lecture notes, slides, or videos.)
Communication complexity (sublinear communication)
Classes
- P. Harsha, M. Mahajan, and J. Radhakrishnan. Communication Complexity. TIFR & IMSc, Monsoon Semester 2011-12.
Workshops
- Information Complexity and Applications at STOC 2013.
- Communication Complexity and Applications in Banff, 2014.
Compressed sensing (sublinear measurement)
Classes
- P. Indyk. Sketching, streaming, and sub-linear space algorithms. MIT, Fall 2007.
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010.
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Spring 2013.
Property testing and sublinear-time algorithms
Classes
- R. Rubinfeld and E. Ben-Sasson. Sublinear Time Algorithms. MIT, Fall 2004.
- R. Rubinfeld. Sublinear Time Algorithms. MIT, Spring 2007.
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010.
- S. Raskhodnikova. Sublinear Algorithms. Penn State, Spring 2012.
- T. Sauerwald. Sublinear Algorithms. Max Planck Institut, Winter Semester 2012.
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Spring 2013.
- G. Yaroslavtsev. Sublinear Algorithms for Big Data. University of Buenos Aires, Summer 2014.
News
Surveys
- E. Fischer. The art of uninformed decisions: a primer to property testing. 2001.
- D. Ron. Property Testing. Handbook of Randomized Computing, Vol. II, 2001.
- R. Rubinfeld. Sublinear time algorithms. Proceedings of the International Congress of Mathematicians, 2006.
- D. Ron. Property testing: a learning theory perspective. 2008.
- A. Czumaj and C. Sohler. Sublinear-time algorithms. In Property Testing. Current Research and Surveys. 2010.
- O. Goldreich. Introduction to testing graph properties. 2010.
- R. Rubinfeld and A. Shapira. Sublinear time algorithms. SIAM Journal on Discrete Mathematics 25, 2011.
- R. Rubinfeld. Taming big probability distributions. XRDS, 2012.
- A. Montanaro and R. de Wolf. A Survey of Quantum Property Testing. 2013.
- C. Canonne. A Survey on Distribution Testing: Your Data is Big. But is it Blue? 2015.
- O. Goldreich. Notes for the first lecture in a course on Property Testing. 2016.
Streaming algorithms
Classes
- P. Indyk. Sketching, streaming, and sub-linear space algorithms. MIT, Fall 2007.
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010.
- A. McGregor. Data streams and massive data. University of Massachusetts in Amherst, Spring 2012.
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Spring 2013.
- J. Nelson. Algorithms for Big Data. Harvard, Fall 2013.
- G. Yaroslavtsev. Sublinear Algorithms for Big Data. University of Buenos Aires, Summer 2014.
Surveys
- S. Muthukrishnan. Data streams: algorithms and applications. Now Publishers Inc, 2005.
- A. McGregor. Graph Stream Algorithms: A Survey. 2013.
Workshops
- Workshop on Streaming Graph Algorithms at the Sandia National Laboratories, 2014.
