Difference between revisions of "Resources"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (This should probably be replaced by a link to the book by Oded when it's ready.)
(Updated the link for the book by Bhattacharyya and Yoshida.)
 
(7 intermediate revisions by 4 users not shown)
Line 4: Line 4:
  
 
== Communication complexity (sublinear communication) ==
 
== Communication complexity (sublinear communication) ==
=== Classes ===
+
=== 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.  
  
Line 12: Line 12:
  
 
== Compressed sensing (sublinear measurement) ==
 
== Compressed sensing (sublinear measurement) ==
=== Classes ===
+
=== 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 ==
=== Classes ===
+
=== 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 26: Line 31:
 
* 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 ''Sublinear Algorithms for Big Data.''] University of Buenos Aires, Summer 2014.
 
* 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 42: Line 49:
 
* C. Canonne. [http://eccc.hpi-web.de/report/2015/063/ ''A Survey on Distribution Testing: Your Data is Big. But is it Blue?''] 2015.
 
* 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.
 
* 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 ==
=== Classes ===
+
=== 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 51: Line 61:
 
* 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.
 
* 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 58: Line 69:
 
=== Workshops ===
 
=== Workshops ===
 
* [http://wsga.sandia.gov/presentations.html Workshop on Streaming Graph Algorithms] at the Sandia National Laboratories, 2014.
 
* [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

(Please add links only to class and workshop websites that provide lecture notes, slides, or videos.)

Communication complexity (sublinear communication)[edit]

Courses[edit]

Workshops[edit]

Compressed sensing (sublinear measurement)[edit]

Courses[edit]

Property testing and sublinear-time algorithms[edit]

Books[edit]

Courses[edit]

News[edit]

Surveys[edit]

Workshops[edit]

Streaming algorithms[edit]

Courses[edit]

Surveys[edit]

Workshops[edit]