Sublinear Algorithms Fall 2021

This is the second part of the elective course titled Advanced Algorithms. The first part of Advanced Algorithms, taught by Prajakta Nimbhorkar, covered various aspects of designing and analyzing randomized algorithms. This second part will cover topics from the field of Sublinear Algorithms.

There is no textbook for the course. Lectures will be based on research papers, which are listed under the references section. Most of these papers can be downloaded from the respective authors' webpages or public open access repositories. We have also included a non-comprehensive list of courses on sublinear algorithms offered at other universities. 

Instructor: Nithin Varma

Lectures: 17:00 to 18:15 on Wednesdays and Fridays; Lectures will be online on Zoom. The Zoom link is posted on the Moodle page for the course.

References

[CRT05] Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time.
SIAM J. Comput. 34(6): 1370-1379 (2005)

[GR02] Oded Goldreich, Dana Ron: Property Testing in Bounded Degree Graphs. Algorithmica 32(2): 302-343 (2002)

[EKKRV00] Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. J. Comput. Syst. Sci. 60(3): 717-751 (2000)

[DGLRRS99] Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky: Improved Testing Algorithms for Monotonicity. RANDOM-APPROX 1999: 97-108

[GGLRS00] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky: Testing Monotonicity. Comb. 20(3): 301-337 (2000)

[BRY14] Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev: Lp-testing. STOC 2014: 164-173

[BJKST02] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan: Counting Distinct Elements in a Data Stream. RANDOM 2002: 1-10

[AMS99] Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137-147 (1999)

[M78] Robert Morris (Bell Labs): Counting large numbers of events in small registers. Communications of the ACM (CACM). (1978)

[Y77] Andrew Yao: Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). FOCS 1977: 222-227

[RTVX11] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie: Fast Local Computation Algorithms. ICS 2011: 223-238

[ACK19] Sepehr Assadi, Yu Chen, Sanjeev Khanna: Sublinear Algorithms for (Δ + 1) Vertex Coloring. SODA 2019: 767-786

Other courses on Sublinear Algorithms

• Sublinear Algorithms by Sofya Raskhonikova, Boston University

• Sublinear Time Algorithms by Ronitt Rubinfeld, MIT

• Sublinear Algorithms by Sepehr Assadi, Rutgers University

• Sublinear Algorithms by Eric Price, U Texas

• Algorithms for Big Data by Chandra Chekuri, University of Illinois Urbana Champagne

• Data Stream Algorithms by Amit Chakrabarti, Dartmouth College

• Sketching Algorithms by Jelani Nelson, UC Berkeley