Difference between revisions of "Resources"
| Line 3: | Line 3: | ||
(Please add links only to class websites that provide lecture notes and/or slides.) | (Please add links only to class websites that provide lecture notes and/or slides.) | ||
| − | == Communication | + | == Communication complexity (sublinear communication) == |
=== Classes === | === Classes === | ||
| − | * P. Harsha, M. Mahajan, and J. Radhakrishnan. | + | * P. Harsha, M. Mahajan, and J. Radhakrishnan. [http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/ ''Communication Complexity.''] TIFR & IMSc, Monsoon Semester 2011-12. |
== Compressed sensing (sublinear measurement) == | == Compressed sensing (sublinear measurement) == | ||
=== Classes === | === Classes === | ||
| − | * P. Indyk. | + | * 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. | + | * P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/fa10/6.896/ ''Sublinear Algorithms.''] MIT, Fall 2010. |
== Property testing and sublinear-time algorithms == | == Property testing and sublinear-time algorithms == | ||
=== Classes === | === Classes === | ||
| − | * R. Rubinfeld and E. Ben-Sasson. | + | * 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. | + | * 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. | |
=== Surveys === | === 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. | + | * R. Rubinfeld and A. Shapira. [http://www.math.tau.ac.il/~asafico/sublinear.pdf ''Sublinear time algorithms.''] SIAM Journal on Discrete Mathematics 25, 2011. |
== Streaming algorithms == | == Streaming algorithms == | ||
=== Classes === | === Classes === | ||
| − | * A. Chakrabarti. | + | * A. Chakrabarti. [http://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/ ''Data Stream Algorithms.''] Dartmouth, Fall 2011. |
| − | * P. Indyk. ''Sketching, streaming, and sub-linear space algorithms.'' MIT, Fall 2007. http://stellar.mit.edu/S/course/6/ | + | * 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. | |
=== Surveys === | === Surveys === | ||
| − | * S. Muthukrishnan. ''Data streams: algorithms and applications.'' Now Publishers Inc, 2005. | + | * S. Muthukrishnan. [http://algo.research.googlepages.com/eight.ps ''Data streams: algorithms and applications.''] Now Publishers Inc, 2005. |
__FORCETOC__ | __FORCETOC__ | ||
Revision as of 03:41, 27 December 2012
Contents
(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. Communication Complexity. TIFR & IMSc, Monsoon Semester 2011-12.
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.
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.
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. Rubinfield. 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.
Streaming algorithms
Classes
- A. Chakrabarti. Data Stream Algorithms. Dartmouth, Fall 2011.
- 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.
Surveys
- S. Muthukrishnan. Data streams: algorithms and applications. Now Publishers Inc, 2005.
