Editing Resources

{{DISPLAYTITLE:Resources on Sublinear Algorithms}}
__TOC__
(Please add links only to class websites that provide lecture notes and/or slides.)

== Communication complexity (sublinear communication) ==
=== Classes ===
*  P. Harsha, M. Mahajan, and J. Radhakrishnan. [http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/ ''Communication Complexity.''] TIFR &amp; IMSc, Monsoon Semester 2011-12. 

=== Workshops ===
* [http://www.cs.princeton.edu/~mbraverm/pmwiki/index.php?n=Research.STOC13Workshop Information Complexity and Applications] at STOC 2013.

== Compressed sensing (sublinear measurement) ==
=== Classes ===
* P. Indyk. [http://stellar.mit.edu/S/course/6/fa07/6.895/ ''Sketching, streaming, and sub-linear space algorithms.''] MIT, Fall 2007. 
* P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/fa10/6.896/ ''Sublinear Algorithms.''] MIT, Fall 2010. 
* P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/sp13/6.893/ ''Sublinear Algorithms.''] MIT, Spring 2013. 

== Property testing and sublinear-time algorithms ==
=== Classes ===
* R. Rubinfeld and E. Ben-Sasson. [http://people.csail.mit.edu/ronitt/COURSE/F04/index.html ''Sublinear Time Algorithms.''] MIT, Fall 2004. 
* R. Rubinfeld. [http://people.csail.mit.edu/ronitt/COURSE/S07/ ''Sublinear Time Algorithms.''] MIT, Spring 2007. 
* P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/fa10/6.896/ ''Sublinear Algorithms.''] MIT, Fall 2010. 
* S. Raskhodnikova. [http://www.cse.psu.edu/~sofya/sublinear598/ ''Sublinear Algorithms.''] Penn State, Spring 2012.
* T. Sauerwald. [http://www.mpi-inf.mpg.de/departments/d1/teaching/ws12/sublinear/ ''Sublinear Algorithms.''] Max Planck Institut, Winter Semester 2012.
* P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/sp13/6.893/ ''Sublinear Algorithms.''] MIT, Spring 2013.
* G. Yaroslavtsev [http://grigory.us/big-data.html "Sublinear Algorithms for Big Data."] University of Buenos Aires, Summer 2014.

=== News ===
* Blog [http://ptreview.sublinear.info/ ''Property Testing Review.''] 

=== Surveys ===
* E. Fischer. [http://www.cs.technion.ac.il/~eldar/surv.ps ''The art of uninformed decisions: a primer to property testing.''] 2001. 
* D. Ron. [http://www.eng.tau.ac.il/~danar/Public-pdf/tut.pdf ''Property Testing.''] Handbook of Randomized Computing, Vol. II, 2001. 
* R. Rubinfield. [http://www.icm2006.org/proceedings/Vol_III/contents/ICM_Vol_3_53.pdf ''Sublinear time algorithms.''] Proceedings of the International Congress of Mathematicians, 2006. 
* D. Ron. [http://www.eng.tau.ac.il/~danar/Public-pdf/fnt-ml.pdf ''Property testing: a learning theory perspective.''] 2008. 
* A. Czumaj and C. Sohler. [http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Draft-Survey-Sublinear.pdf ''Sublinear-time algorithms.''] In ''Property Testing. Current Research and Surveys.'' 2010. 
* O. Goldreich. [http://www.wisdom.weizmann.ac.il/~oded/p_tgp.html ''Introduction to testing graph properties.''] 2010.
* R. Rubinfeld and A. Shapira. [http://www.math.tau.ac.il/~asafico/sublinear.pdf ''Sublinear time algorithms.''] SIAM Journal on Discrete Mathematics 25, 2011. 
* A. Montanaro and R. de Wolf. [http://arxiv.org/abs/1310.2035 ''A Survey of Quantum Property Testing.''] 2013.

== Streaming algorithms ==
=== Classes ===
* P. Indyk. [http://stellar.mit.edu/S/course/6/fa07/6.895/ ''Sketching, streaming, and sub-linear space algorithms.''] MIT, Fall 2007. 
* P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/fa10/6.896/ ''Sublinear Algorithms.''] MIT, Fall 2010. 
* A. McGregor. [http://people.cs.umass.edu/~mcgregor/courses/CS711S12/ ''Data streams and massive data.''] University of Massachusetts in Amherst, Spring 2012. 
* P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/sp13/6.893/ ''Sublinear Algorithms.''] MIT, Spring 2013.
* J. Nelson. [http://people.seas.harvard.edu/~minilek/cs229r/ ''Algorithms for Big Data.''] Harvard, Fall 2013.

=== Surveys ===
* S. Muthukrishnan. [http://algo.research.googlepages.com/eight.ps ''Data streams: algorithms and applications.''] Now Publishers Inc, 2005. 
* A. McGregor. [http://people.cs.umass.edu/~mcgregor/papers/13-graphsurvey.pdf ''Graph Stream Algorithms: A Survey.''] 2013.

__FORCETOC__