Editing Resources

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 1: Line 1:
 
{{DISPLAYTITLE:Resources on Sublinear Algorithms}}
 
{{DISPLAYTITLE:Resources on Sublinear Algorithms}}
 
__TOC__
 
__TOC__
−
(Please add links only to class and workshop websites that provide lecture notes, slides, or videos.)
+
(Please add links only to class websites that provide lecture notes and/or slides.)
  
 
== Communication complexity (sublinear communication) ==
 
== Communication complexity (sublinear communication) ==
−
=== Courses ===
+
=== Classes ===
 
*  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 ===
+
=== Classes ===
 
* 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 ===
+
=== Classes ===
−
* 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 31: Line 26:
 
* 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 40: Line 33:
 
* 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. 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.  
+
* 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.  
 
* 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 ===
+
=== Classes ===
 
* 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 61: Line 48:
 
* 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 67: Line 53:
 
* 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__

Please note that all contributions to Open Problems in Sublinear Algorithms may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Open Problems in Sublinear Algorithms:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)
Retrieved from "https://sublinear.info/index.php?title=Resources"