# CS 591 Sublinear Algorithms (Fall 2020)

## General Information

Time and location: Tuesday/Thursday 12:30PM-1:45PM
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.

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

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) AGM12 HW3 due
Tu, Oct 13 Monday Schedule
12 Th, Oct 15 Testing properties of dense graphs; bipartiteness (Slides) GGR98 HW3 due (extended deadline)
13 Tu, Oct 20 Approximate Max-Cut (Slides) GGR98
14 Th, Oct 22 Testing triangle-freeness; Regularity Lemma (Slides) AFKS00
15 Tu, Oct 27 Testing triangle-freeness. Triangle-removal lemma. Testing other properties of dense graphs. Behrend's construction of progression-free sets. (Slides) Alon02
16 Th, Oct 29 Lower bound for testing triangle-freeness. Canonical testers in the dense-graph model (in class exercise). (Slides) Alon02, GT03 Project progress report due
17 Tu, Nov 3 Approximating the average degree of a graph (Slides)
18 Th, Nov 5 Testing linearity of Boolean functions (Slides) BLR93 HW4 out
19 Tu, Nov 10 Finish linearity testing. Tolerant testing and distance approximation. (Slides)
20 Th, Nov 12 Approximating distance to sortedness for 0/1 sequences. (Slides) HW4 due
21 Tu, Nov 17 Gap Edit Distance
22 Th, Nov 19 L_p-Testing (Slides)
23 Tu, Nov 24 L_p-Testing of monotonicity. Work investment strategy (Slides)
Nov 25-29 Thanksgiving Recess
24 Tu, Dec 1 Local Computation Algorithm for Maximal Independent Set (Slides)
25 Th, Dec 3 Local Computation Algorithm for Maximal Independent Set (Slides) Project final report due
26 Tu, Dec 8 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.