# 0368.416701 Sublinear time algorithms

## Instructor: Ronitt Rubinfeld Fall 2014

### Brief Course Description

This course will focus on the design of algorithms that are restricted to run in sublinear time, and thus can view only a very small portion of the data. The study of sublinear time algorithms has been applied to problems from a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. This course will introduce many of the various techniques that have been applied to analyzing such algorithms.

Will be based on the solutions to homework exercises, a class project and class participation.

### Prerequisites

Algorithms. Exposure to computational complexity is helpful but not required.

### Time and location

The course will take place on Mondays, 13:00-16:00, in Shenkar 105.

### Course Information Handout

More details on syllabus, grading, etc. (pdf) (see also "useful pointers" below)

### Announcements

• Turn in HW 6 to box 370 in Schreiber
• Go here to sign up for PROJECT PRESENTATIONS. Prepare at most 5 minutes -- slides are fine. I'd also like a short writeup (about a paragraph) containing what you did, what you found, and possibly what you would have liked to have done, some good open questions,... If your project involved code or a proof, include the code/proof as an appendix.
• January 5 lecture cancelled! Instead, lectures will be moved back a week, and project presentations will be done at a different time. Stay tuned for a sign up sheet for project presentations.
• If you are not familiar with Markov, Chebyshev and Hoeffding/Chernoff bounds, please read about them in one or more of the descriptions given below in "useful pointers".

### Lecture notes and VERY tentative plan

1. Lecture 1 (10/27): Introductory remarks. Property testing. Diameter. Monotonicity. Element distinctness. Quick probability review. scribe notes
2. Lecture 2 (11/3): Property testing of element distinctness. Testing properties of distributions. Uniformity. scribe notes
3. Lecture 3 (11/10): More testing properties of distributions. scribe notes
4. Lecture 4 (11/17): Estimating the number of connected components, minimum spanning tree. Distributed computing vs. sublinear time: a reduction. scribe notes
5. Lecture 5 (11/24): Approximating vertex cover and maximal matching. scribe notes version 1 , scribe notes version 2
6. Lecture 6 (12/1): Testing planarity via H-minor freeness. Approximating the average degree. scribe notes.
7. Lecture 7 (12/8): Lower bound techniques. Yao's method. Communication complexity vs. property testing. scribe notes.
8. Lecture 8 (12/15): Property testing in dense graphs: bipartiteness. scribe notes.
9. Lecture 9 (12/22): Property testing in dense graphs: triangle-freeness, Szemeredi's regularity lemma. scribe notes.
10. Lecture 10 (12/29): Property testing in dense graphs: a lower bound in epsilon. scribe notes.
11. Lecture 11 (1/13): Testing boolean functions: Fourier basics. Testing linearity. scribe notes.
12. Lecture 12 (1/20): Testing boolean functions: dictatorships. Testing approximate correctness of delegated computations. scribe notes. ">