# Difference between revisions of "Resources"

Line 4: | Line 4: | ||

== 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. | ||

Line 12: | Line 12: | ||

== 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. | ||

Line 18: | Line 18: | ||

== Property testing and sublinear-time algorithms == | == Property testing and sublinear-time algorithms == | ||

− | === | + | === Books === |

+ | * A. Bhattacharyya and Y. Yoshida. [http://propertytestingbook.wordpress.com ''Property Testing.''] In preparation. | ||

+ | * 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 30: | ||

* 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 | + | * 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 | + | * R. Servedio. [http://www.cs.columbia.edu/~rocco/Teaching/S14/# ''Sublinear Time Algorithms in Learning and Property Testing.''] Columbia, Spring 2014. |

=== News === | === News === | ||

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

− | |||

− | |||

− | |||

− | |||

=== Surveys === | === Surveys === | ||

Line 51: | Line 51: | ||

=== Workshops === | === 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. | * [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 and R. Rubinfeld. [http://stellar.mit.edu/S/course/6/fa10/6.896/ ''Sublinear Algorithms.''] MIT, Fall 2010. |

## Revision as of 04:18, 8 April 2016

## Contents

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

## Communication complexity (sublinear communication)

### Courses

- P. Harsha, M. Mahajan, and J. Radhakrishnan.
*Communication Complexity.*TIFR & IMSc, Monsoon Semester 2011-12.

### Workshops

- Information Complexity and Applications at STOC 2013.
- Communication Complexity and Applications in Banff, 2014.

## Compressed sensing (sublinear measurement)

### Courses

- 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.

## Property testing and sublinear-time algorithms

### Books

- A. Bhattacharyya and Y. Yoshida.
*Property Testing.*In preparation. - O. Goldreich.
*Introduction to Property Testing.*In preparation.

### Courses

- 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

### 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. 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

- DIMACS Workshop on Big Data through the Lens of Sublinear Algorithms at DIMACS Center, CoRE Building, Rutgers University, 2015.

## Streaming algorithms

### Courses

- 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.

### Surveys

- S. Muthukrishnan.
*Data streams: algorithms and applications.*Now Publishers Inc, 2005. - A. McGregor.
*Graph Stream Algorithms: A Survey.*2013.

### Workshops

- 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.