Difference between revisions of "Resources"
(This class doesn't cover sublinear-TIME or property testing. Let me know if I'm wrong.) |
(Updated the link for the book by Bhattacharyya and Yoshida.) |
||
| (14 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{DISPLAYTITLE:Resources on Sublinear Algorithms}} | {{DISPLAYTITLE:Resources on Sublinear Algorithms}} | ||
__TOC__ | __TOC__ | ||
| − | (Please add links only to class websites that provide lecture notes | + | (Please add links only to class and workshop websites that provide lecture notes, slides, or videos.) |
== Communication complexity (sublinear communication) == | == Communication complexity (sublinear communication) == | ||
| − | === | + | === Courses === |
* 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. | * 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. | ||
=== Workshops === | === Workshops === | ||
* [http://www.cs.princeton.edu/~mbraverm/pmwiki/index.php?n=Research.STOC13Workshop Information Complexity and Applications] at STOC 2013. | * [http://www.cs.princeton.edu/~mbraverm/pmwiki/index.php?n=Research.STOC13Workshop Information Complexity and Applications] at STOC 2013. | ||
| + | * [https://www.birs.ca/events/2014/5-day-workshops/14w5164 Communication Complexity and Applications] in Banff, 2014. | ||
== Compressed sensing (sublinear measurement) == | == Compressed sensing (sublinear measurement) == | ||
| − | === | + | === Courses === |
* P. Indyk. [http://stellar.mit.edu/S/course/6/fa07/6.895/ ''Sketching, streaming, and sub-linear space algorithms.''] MIT, Fall 2007. | * 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/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. | * P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/sp13/6.893/ ''Sublinear Algorithms.''] MIT, Spring 2013. | ||
| + | * E. Price. [http://www.cs.utexas.edu/~ecprice/courses/sublinear/ ''Sublinear Algorithms.''] UT Austin, Fall 2014. | ||
== Property testing and sublinear-time algorithms == | == Property testing and sublinear-time algorithms == | ||
| − | === | + | === Books === |
| + | * A. Bhattacharyya and Y. Yoshida. [https://link.springer.com/book/10.1007/978-981-16-8622-1 ''Property Testing.''] Springer Singapore, 2022. | ||
| + | * O. Goldreich. [http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html ''Introduction to Property Testing.''] In preparation. | ||
| + | |||
| + | === Courses === | ||
* R. Rubinfeld and E. Ben-Sasson. [http://people.csail.mit.edu/ronitt/COURSE/F04/index.html ''Sublinear Time Algorithms.''] MIT, Fall 2004. | * 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. | * R. Rubinfeld. [http://people.csail.mit.edu/ronitt/COURSE/S07/ ''Sublinear Time Algorithms.''] MIT, Spring 2007. | ||
| Line 24: | Line 30: | ||
* T. Sauerwald. [http://www.mpi-inf.mpg.de/departments/d1/teaching/ws12/sublinear/ ''Sublinear Algorithms.''] Max Planck Institut, Winter Semester 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. | * 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 | + | * G. Yaroslavtsev. [http://grigory.us/big-data.html ''Sublinear Algorithms for Big Data.''] University of Buenos Aires, Summer 2014. |
| + | * E. Price. [http://www.cs.utexas.edu/~ecprice/courses/sublinear/ ''Sublinear Algorithms.''] UT Austin, Fall 2014. | ||
| + | * R. Servedio. [http://www.cs.columbia.edu/~rocco/Teaching/S14/# ''Sublinear Time Algorithms in Learning and Property Testing.''] Columbia, Spring 2014. | ||
=== News === | === News === | ||
| Line 32: | Line 40: | ||
* E. Fischer. [http://www.cs.technion.ac.il/~eldar/surv.ps ''The art of uninformed decisions: a primer to property testing.''] 2001. | * 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. | * D. Ron. [http://www.eng.tau.ac.il/~danar/Public-pdf/tut.pdf ''Property Testing.''] Handbook of Randomized Computing, Vol. II, 2001. | ||
| − | * R. | + | * R. Rubinfeld. [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. | * 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. | * 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. | * 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. | * R. Rubinfeld and A. Shapira. [http://www.math.tau.ac.il/~asafico/sublinear.pdf ''Sublinear time algorithms.''] SIAM Journal on Discrete Mathematics 25, 2011. | ||
| + | * R. Rubinfeld. [https://dl.acm.org/citation.cfm?id=2331052 ''Taming big probability distributions.''] XRDS, 2012. | ||
* A. Montanaro and R. de Wolf. [http://arxiv.org/abs/1310.2035 ''A Survey of Quantum Property Testing.''] 2013. | * A. Montanaro and R. de Wolf. [http://arxiv.org/abs/1310.2035 ''A Survey of Quantum Property Testing.''] 2013. | ||
| + | * C. Canonne. [http://eccc.hpi-web.de/report/2015/063/ ''A Survey on Distribution Testing: Your Data is Big. But is it Blue?''] 2015. | ||
| + | * O. Goldreich. [http://www.wisdom.weizmann.ac.il/~oded/PDF/pt-intro.pdf ''Notes for the first lecture in a course on Property Testing.''] 2016. | ||
| + | |||
| + | === Workshops === | ||
| + | * [http://dimacs.rutgers.edu/Workshops/ParallelAlgorithms/ DIMACS Workshop on Big Data through the Lens of Sublinear Algorithms] at DIMACS Center, CoRE Building, Rutgers University, 2015. | ||
== Streaming algorithms == | == Streaming algorithms == | ||
| − | === | + | === Courses === |
* P. Indyk. [http://stellar.mit.edu/S/course/6/fa07/6.895/ ''Sketching, streaming, and sub-linear space algorithms.''] MIT, Fall 2007. | * 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/fa10/6.896/ ''Sublinear Algorithms.''] MIT, Fall 2010. | ||
| Line 46: | Line 60: | ||
* P. Indyk and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/sp13/6.893/ ''Sublinear Algorithms.''] MIT, Spring 2013. | * 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. | * J. Nelson. [http://people.seas.harvard.edu/~minilek/cs229r/ ''Algorithms for Big Data.''] Harvard, Fall 2013. | ||
| + | * G. Yaroslavtsev. [http://grigory.us/big-data.html ''Sublinear Algorithms for Big Data.''] University of Buenos Aires, Summer 2014. | ||
| + | * E. Price. [http://www.cs.utexas.edu/~ecprice/courses/sublinear/ ''Sublinear Algorithms.''] UT Austin, Fall 2014. | ||
=== Surveys === | === Surveys === | ||
| Line 51: | Line 67: | ||
* A. McGregor. [http://people.cs.umass.edu/~mcgregor/papers/13-graphsurvey.pdf ''Graph Stream Algorithms: A Survey.''] 2013. | * A. McGregor. [http://people.cs.umass.edu/~mcgregor/papers/13-graphsurvey.pdf ''Graph Stream Algorithms: A Survey.''] 2013. | ||
| + | === Workshops === | ||
| + | * [http://wsga.sandia.gov/presentations.html Workshop on Streaming Graph Algorithms] at the Sandia National Laboratories, 2014. | ||
| + | * [http://dimacs.rutgers.edu/Workshops/ParallelAlgorithms/ DIMACS Workshop on Big Data through the Lens of Sublinear Algorithms] at DIMACS Center, CoRE Building, Rutgers University, 2015. | ||
__FORCETOC__ | __FORCETOC__ | ||
Latest revision as of 00:50, 27 January 2023
Contents
(Please add links only to class and workshop websites that provide lecture notes, slides, or videos.)
Communication complexity (sublinear communication)[edit]
Courses[edit]
- P. Harsha, M. Mahajan, and J. Radhakrishnan. Communication Complexity. TIFR & IMSc, Monsoon Semester 2011-12.
Workshops[edit]
- Information Complexity and Applications at STOC 2013.
- Communication Complexity and Applications in Banff, 2014.
Compressed sensing (sublinear measurement)[edit]
Courses[edit]
- 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.
- E. Price. Sublinear Algorithms. UT Austin, Fall 2014.
Property testing and sublinear-time algorithms[edit]
Books[edit]
- A. Bhattacharyya and Y. Yoshida. Property Testing. Springer Singapore, 2022.
- O. Goldreich. Introduction to Property Testing. In preparation.
Courses[edit]
- 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.
- E. Price. Sublinear Algorithms. UT Austin, Fall 2014.
- R. Servedio. Sublinear Time Algorithms in Learning and Property Testing. Columbia, Spring 2014.
News[edit]
Surveys[edit]
- 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.
Workshops[edit]
- DIMACS Workshop on Big Data through the Lens of Sublinear Algorithms at DIMACS Center, CoRE Building, Rutgers University, 2015.
Streaming algorithms[edit]
Courses[edit]
- 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.
- E. Price. Sublinear Algorithms. UT Austin, Fall 2014.
Surveys[edit]
- S. Muthukrishnan. Data streams: algorithms and applications. Now Publishers Inc, 2005.
- A. McGregor. Graph Stream Algorithms: A Survey. 2013.
Workshops[edit]
- Workshop on Streaming Graph Algorithms at the Sandia National Laboratories, 2014.
- DIMACS Workshop on Big Data through the Lens of Sublinear Algorithms at DIMACS Center, CoRE Building, Rutgers University, 2015.
