Difference between revisions of "Resources"
m |
|||
| Line 1: | Line 1: | ||
{{DISPLAYTITLE:Resources on Sublinear Algorithms}} | {{DISPLAYTITLE:Resources on Sublinear Algorithms}} | ||
| − | Please add links only to class websites that provide lecture notes and/or slides. | + | __TOC__ |
| + | (Please add links only to class websites that provide lecture notes and/or slides.) | ||
| + | == Compressed sensing (sublinear measurement) == | ||
| + | === Classes === | ||
| + | * P. Indyk. ''Sketching, streaming, and sub-linear space algorithms.'' MIT, Fall 2007. http://stellar.mit.edu/S/course/6/fa07/6.895/ | ||
| + | * P. Indyk and R. Rubinfeld. ''Sublinear Algorithms.'' MIT, Fall 2010. http://stellar.mit.edu/S/course/6/fa10/6.896/ | ||
| + | |||
== Property testing and sublinear-time algorithms == | == Property testing and sublinear-time algorithms == | ||
=== Classes === | === Classes === | ||
| − | * R. Rubinfeld and E. Ben- Sasson. ''Sublinear Time Algorithms.'' MIT, Fall 2004. http://people.csail.mit.edu/ronitt/COURSE/F04/index.html | + | * R. Rubinfeld and E. Ben-Sasson. ''Sublinear Time Algorithms.'' MIT, Fall 2004. http://people.csail.mit.edu/ronitt/COURSE/F04/index.html |
* R. Rubinfeld. ''Sublinear Time Algorithms.'' MIT, Spring 2007. http://people.csail.mit.edu/ronitt/COURSE/S07/ | * R. Rubinfeld. ''Sublinear Time Algorithms.'' MIT, Spring 2007. http://people.csail.mit.edu/ronitt/COURSE/S07/ | ||
* P. Indyk and R. Rubinfeld. ''Sublinear Algorithms.'' MIT, Fall 2010. http://stellar.mit.edu/S/course/6/fa10/6.896/ | * P. Indyk and R. Rubinfeld. ''Sublinear Algorithms.'' MIT, Fall 2010. http://stellar.mit.edu/S/course/6/fa10/6.896/ | ||
Revision as of 16:57, 12 December 2012
Contents
(Please add links only to class websites that provide lecture notes and/or slides.)
Compressed sensing (sublinear measurement)
Classes
- P. Indyk. Sketching, streaming, and sub-linear space algorithms. MIT, Fall 2007. http://stellar.mit.edu/S/course/6/fa07/6.895/
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010. http://stellar.mit.edu/S/course/6/fa10/6.896/
Property testing and sublinear-time algorithms
Classes
- R. Rubinfeld and E. Ben-Sasson. Sublinear Time Algorithms. MIT, Fall 2004. http://people.csail.mit.edu/ronitt/COURSE/F04/index.html
- R. Rubinfeld. Sublinear Time Algorithms. MIT, Spring 2007. http://people.csail.mit.edu/ronitt/COURSE/S07/
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010. http://stellar.mit.edu/S/course/6/fa10/6.896/
Surveys
- E. Fischer. The art of uninformed decisions: a primer to property testing. 2001. http://www.cs.technion.ac.il/~eldar/surv.ps
- D. Ron. Property Testing. Handbook of Randomized Computing, Vol. II, 2001. http://www.eng.tau.ac.il/~danar/Public-pdf/tut.pdf
- R. Rubinfield. Sublinear time algorithms. Proceedings of the International Congress of Mathematicians, 2006. http://www.icm2006.org/proceedings/Vol_III/contents/ICM_Vol_3_53.pdf
- D. Ron. Property testing: a learning theory perspective. 2008. http://www.eng.tau.ac.il/~danar/Public-pdf/fnt-ml.pdf
- O. Goldreich. Introduction to testing graph properties. 2010. http://www.wisdom.weizmann.ac.il/~oded/p_tgp.html
- R. Rubinfeld and A. Shapira. Sublinear time algorithms. SIAM Journal on Discrete Mathematics 25, 2011. http://www.math.tau.ac.il/~asafico/sublinear.pdf
Streaming algorithms
Classes
- P. Indyk. Sketching, streaming, and sub-linear space algorithms. MIT, Fall 2007. http://stellar.mit.edu/S/course/6/fa07/6.895/
- P. Indyk and R. Rubinfeld. Sublinear Algorithms. MIT, Fall 2010. http://stellar.mit.edu/S/course/6/fa10/6.896/
- A. McGregor. Data streams and massive data. University of Massachusetts in Amherst, Spring 2012. http://people.cs.umass.edu/~mcgregor/courses/CS711S12/
Surveys
- S. Muthukrishnan. Data streams: algorithms and applications. Now Publishers Inc, 2005. http://algo.research.googlepages.com/eight.ps
