CS 591 Sublinear Algorithms (Fall 2020)

General Information

Time and location: Tuesday/Thursday 12:30PM-1:45PM
Instructor: Sofya Raskhodnikova
Office hours: Wednesday 1PM-2:30PM (on zoom)

Prerequisites

CS 537, proficiency in understanding and writing mathematical proofs

Course description

This course will cover the design and analysis of algorithms that are restricted to run in sublinear time. Such algorithms are typically randomized and produce only approximate answers. A characteristic feature of sublinear algorithms is that they do not have time to access the entire input. Therefore, input representation and the model for accessing the input play an important role. We will study different models appropriate for sublinear algorithms. The course will cover sublinear algorithms discovered in a variety of areas, including graph theory, algebra, geometry, and discrete mathematics, and introduce many techniques that are applied to analyzing sublinear algorithms.

Grading

Students will be evaluated based on class participation, solutions to about 4-5 homework assignments, taking lecture notes about 1-2 times per person, and the final project.

Lectures

Lec Date Topics References Reading/Homework
1 Th, Sep 3 Introduction. Basic models for sublinear-time computation. Simple examples of sublinear algorithms. (Slides) RS96, GGR98, Ras03, EKKRV00, Fis04 Ras03, Ras15; Course Information; Probabilistic Inequalities Review; HW1 out
2 Tu, Sep 8 Properties of lists and functions. Testing if a list is sorted/Lipschitz and if a function is monotone. (Slides) DGLRRS99, BGJRW09, Ras10, JR13
3 Th, Sep 10 Testing a bounded-degree graph is connected. Approximating the number of connected components and MST weight. (Slides) GR02, CRT05 HW1 due; HW2 out
4 Tu, Sep 15 Methods for proving lower bounds: Yao's principle. (Slides) (covered slides 1-16)
5 Th, Sep 17 Methods for proving lower bounds: Yao's principle and communication complexity. (Slides) FLNRRS02, BBM11 HW2 due
6 Tu, Sep 22 Finish communication complexity. Other models of sublinear time/space computation. Project discussion. (Slides) BBM11
7 Th, Sep 24 Streaming: Distinct Elements; k-wise independence (Slides) AMS99, BJKST02
8 Tu, Sep 29 Streaming: approximate counting; linear sketching; estimating second frequency moment (Slides) Mor78, AMS99
9 Th, Oct 1 Multi-purpose sketches: Count-Min and Count-Sketch; range queries, quantiles, heavy hitters (Slides) CM05, GM07 Project proposal due; HW3 out
10 Tu, Oct 6 Streaming lower bounds via communication complexity (Slides) BJKS04 Rou16 (Chapter 1)
11 Th, Oct 8 Graph streams; linear sketching for connected components; L0 sampling (Slides) HW3 due
Tu, Oct 13 Monday Schedule
12 Th, Oct 15 Testing properties of dense graphs; bipartiteness (Slides) HW3 due (extended deadline)
13 Tu, Oct 20
14 Th, Oct 22
15 Tu, Oct 27
16 Th, Oct 29 Project progress report due
17 Tu, Nov 3
18 Th, Nov 5
19 Tu, Nov 10
20 Th, Nov 12
21 Tu, Nov 17
22 Th, Nov 19
23 Tu, Nov 24
Nov 25-29 Thanksgiving Recess
24 Tu, Dec 1
25 Th, Dec 3 Final project presentations Project final report due
26 Tu, Dec 7 Final project presentations
27 Th, Dec 10 Final project presentations

Resources on sublinear algorithms

(Optional) textbook
Introduction to Property Testing by Oded Goldreich
Latest in property testing
Property testing review
Open problems
A list of open problems

Miscellaneous

LaTeX
Some LaTeX editors: TexShop for Mac, TexStudio for Windows, Overleaf on the web (no installation needed, allows for collaboration).
Not so short intro to LaTeX and a LaTeX tutorial.
Homework template files: tex, pdf, cls, jpg.

Bibliography

Most papers from the list below can be downloaded from the Princeton archive or my webpage.

RS96 Ronitt Rubinfeld, Madhu Sudan, Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal of Computing 1996.
GGR98 Oded Goldreich, Shafi Goldwasser, Dana Ron, Property Testing and its Connection to Learning and Approximation. Journal of ACM 1998, FOCS 1996.
Ras03 Sofya Raskhodnikova, Approximate Testing of Visual Properties. RANDOM-APPROX 2003.
Ras15 Sofya Raskhodnikova, Testing if an Array Is Sorted. Encyclopedia of Algorithms 2015.
RS06 Sofya Raskhodnikova, Adam Smith, A Note on Adaptivity in Testing Properties of Bounded Degree Graphs. Electronic Colloquium on Computational Complexity, Report No. 89, 2006.
EKKRV00 Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan, Spot-Checkers. Journal of Computer System and Sciences 2000, STOC 1998.
Fis04 Eldar Fischer, On the strength of comparisons in property testing. Information and Computation 2004.
DGLRRS99 Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky, Improved Testing Algorithms for Monotonicity. RANDOM-APPROX 1999.
BFJRW09 Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff, Transitive-Closure Spanners. SODA 2009.
Ras10 Sofya Raskhodnikova, Transitive-Closure Spanners: a Survey. In O. Goldreich, editor, Property Testing, LNCS 6390, LNCS State-of-the-Art Surveys, Springer, Heidelberg, 167--196, 2010.
JR13 Madhav Jha, Sofya Raskhodnikova, Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. SIAM Journal on Computing 2013, STOC 11.
GR02 Oded Goldreich, Dana Ron, Property testing in bounded degree graphs. Algorithmica 2002, STOC 1997.
CRT05 Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan, Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM Journal of Computing 2005, ICALP 2001.
FLNRRS02 Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky Monotonicity Testing Over General Poset Domains. STOC 2002.
BBM11 Eric Blais, Joshua Brody, Kevin Matulef, Property Testing Lower Bounds via Communication Complexity. CCC 2011.
AK02 Noga Alon, Michael Krivelevich, Testing k-colorability. SIAM J. Discrete Math. 15 (2002), 211-227.
Alon02 Noga Alon, Testing subgraphs in large graphs. Random Structures and Algorithms 21 (2002), 359-370.
AFKS02 Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451-476.
GT03 Oded Goldreich, Luca Trevisan, Three theorems regarding testing graph properties, Random Struct. Algorithms 23(1): 23-57 (2003)
GR08 Oded Goldreich, Dan Ron, Approximating average parameters of graphs, Random Struct. Algorithms 32(4): 473-493 (2008)
PaRo07 Michal Parnas, Dan Ron, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Theor. Comput. Sci., 381(1-3):183--196 (2007)
NO08 Huy N. Nguyen and Krzysztof Onak, Constant-Time Approximation Algorithms via Local Improvements, FOCS (2008)
ORRR12 Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld, A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size, In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1123--1131 (2012)
Ras99 Sofya Raskhodnikova, Monotonicity Testing, Master's Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1999
CS12 Deeparnab Chakrabarty, C. Seshadhri Optimal bounds for monotonicity and Lipschitz testing over the hypercube. ECCC, TR12-030, 2012.
BBBY12 Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang, Active Property Testing. Manuscript, 2012.
BLR93 Manuel Blum, Michael Luby, Ronitt Rubinfeld, Self-Testing/Correcting with Applications to Numerical Problems. Journal of Computer System and Sciences 1993, STOC 1990.
BCHKS96 M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi, M. Sudan, Linearity testing in characteristic two. IEEE Transactions on Information Theory, Vol. 42, No. 6, pp. 1781--1795, 1996, FOCS 95.
AMS99 Noga Alon, Yossi Matias, Mario Szegedy, The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137–147, 1999.
BJKST02 Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan. Counting Distinct Elements in a Data Steam. RANDOM 02: 1-10, 2002.
Mor78 Robert Morris, Counting Large Numbers of Events in Small Registers. Commun. ACM, 21(10): 840-842, 1978.
CM05 Graham Cormode, S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1): 58-75, 2005
GM07 Sumit Ganguly, Anirban Majumder, CR-precis: A Deterministic Summary Structure for Update Data Streams. ESCAPE 2007: 48-59, 2007
Rou16 Tim Roughgarden, Communication Complexity (for Algorithm Designers). Found. Trends Theor. Comput. Sci. 11(3-4): 217-404, 2016
BJKS04 Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, and D. Sivakumar, An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences 68, 702–732, 2004