Announcements

Welcome to CS590 Sublinear Algorithms!

Course description

Algorithms that compute with a sublinear amount of resources
(time, space, communication) lie at the foundations of data science. They can
be used to analyze data across domains that span from social networks,
financial transactions, or genomic data, to satellite communications or
astronomical data. In this course we will study several sublinear models,
including the sublinear-time model of Property Testing, sublinear-space
streaming models, and sublinear-communication models. We will introduce many of
the combinatorial, algebraic and geometric techniques commonly used in
analyzing very fast algorithms for mathematical objects such as graphs,
strings, distributions, and error-correcting codes.

**Prerequisites:** A course on discrete math, undergraduate algorithms, and mathematical maturity.

Grading

Similar courses elsewhere- Sublinear algorithms, by Sepher Assadi
- Data stream algorithms, by Amit Chakrabarti
- Data stream algorithms, by Andrew McGregor
- Sublinear algorithms, by Sofya Raskhodnikova
- Communication complexity, by Tim Roughgarden
- Sublinear algorithms, by Ronit Rubinfeld
- Essential coding theory, by Madhu Sudan
- Sublinear algorithms for big data, by Qin Zhang

Schedule

- Jan. 19 1. Intro to sublinear models handwritten notes, scribe notes
- Jan. 21 2. Testing connectivity; estimating number of components; estimating weight of MST handwritten notes , scribe notes
- Jan. 26 3. Estimating MST (contd). Estimating average degree handwritten notes , scribe notes
- Jan. 28 4. Avg. degree (contd). Testing triangle freeness handwritten notes
- Feb 2 5. Szemeredi's regularity lemma handwritten notes, scribe notes, E.Croot's notes
- Feb 4 6. Triangle removal lemma handwritten notes, scribe notes
- Feb 9 7. Roth's theorem; Alon's lower bound for testing triangle freeness handwritten notes
- Feb 11 8. Testing linearity via Fourier analysis handwritten notes
- Feb. 16 9. PAC learning. Uniform learning of conjunctions handwritten notes, scribe notes
- Feb. 18 10. Learning via Fourier coefficients (the low-degree algorithm) handwritten notes
- Feb. 23 11.Locally decodable codes handwritten notes
- Feb. 25 12. LDCs from Reed Muller codes and more handwritten notes
- Mar 2 13. Local list decoding of the Hadamard code (Goldreich-Levin) handwritten notes
- Mar 4 14. GL (contd). Applications to pseudorandomness (notes above)
- Mar 9 15. Streaming clusters handwritten notes. A. Chakrabarti's streaming lecture notes
- Mar 11 16. Streaming clusters (contd). Streaming basic graph algorithms handwritten notes
- Mar. 16 17. Streaming for matching problems handwritten notes, scribe notes
- Mar. 18 NO CLASS. (Purdue reading day)
- Mar. 23 18 Project updates. Streaming lower bounds via communication complexity
- Mar. 25 19 Streaming lower bounds via communication complexity handwritten notes, scribe notes.
- Mar. 30 20. Fun and research
- Apr 1 21. Yao's principle for communication/streaming lower bounds handwritten notes, T. Roughgarden's lecture notes, scribe notes
- Apr 6 22. Lower bounds for testing monotonicity from communication handwritten notes
- Apr. 8 23 Sparse recovery in the turnstile model handwritten notes
- Apr. 13 NO CLASS (Purdue reading day)
- Apr. 15 24 Sparse recovery (contd). Graph sketching: deciding connectivity and bipartetenss handwritten notes
- Apr. 20 25 Graph sketching (contd). Triangle counting (see notes above)
- Apr. 22 26 Reseach day
- Apr. 27 27 Guest lecture by Samson Zhou
- Apr. 29 28 Projects presentations