In this class, we will explore the following fundamental question:
what problems can we solve when we are only allowed to examine a very small fraction of the input?
As we will see, this question leads to many deep results and intriguing open problems in different areas of theoretical computer science, including complexity theory, learning theory, property testing, locally-decodable error-correcting codes, and probabilistically-checkable proofs.
- Decision tree complexity of Boolean functions
- Learning theory (with membership queries)
- Property testing
- Locally-decodable and locally-testable error-correcting codes
- Probabilistically-checkable proofs
- Quantum query complexity
The goal of the course will be to see how all these different areas are
connected to each other and to the general theme of sublinear-time
algorithms; to cover a selection of the main results in these areas; and
to explore some fundamental open questions.
This course will assume only a general background in theoretical computer
science. We will use many different tools from the analysis of Boolean
functions, communication complexity, extremal combinatorics, information
theory, and probability theory, but these will be introduced in the course
as they are needed.
Each class starting in week 2 will be divided in two parts. In the first
half of the class, we will discuss the paper of the week. The choice of
papers will alternate between classics of the field and more recent results.
The second half of the class will consist of a lecture covering the
background material in preparation for the next week's paper.
Outside of lecture hours, the course work include reading and
preparing for the weekly discussion sessions on the week's papers, and
conducting a research project on one of the open problems in sublinear-time
algorithms. The grades will be determined as follows.
- 40%: Class participation and discussions
- 60%: Project
- September 12
- Introduction to sublinear-time algorithms and to
Boolean functions. Decision tree complexity.
Paper of the week: Rivest-Vuillemin '76
- September 19
- Exact and PAC learning. Introduction to Fourier analysis of Boolean functions.
Paper of the week: Kushilevitz-Mansour '93
- September 26
- Project ideas.
Paper of the week: None. Project proposal due next week.
- October 3
- Property testing. Testing linearity
Paper of the week: Bellare-Coppersmith-Håstad-Kiwi-Sudan '96
- October 10
- Testing dictator functions and juntas.
Paper of the week: Blais '09
- October 17
- Testing monotonicity. Isoperimetric inequalities for Boolean functions.
Paper of the week: Chakrabarty-Seshadhri '13
- October 24
- Limitations of sublinear-time algorithms. Communication complexity.
Paper of the week: Blais-Brody-Matulef '12
- October 31
- Locally-decodable codes.
Paper of the week: Katz-Trevisan '00
- November 7
- Locally-testable codes. Introduction to the PCP Theorem.
Paper of the week: Arora-Barak, Chapter 11
- November 14
- The PCP Theorem continued.
Paper of the week: Dinur '07
- November 21
- Quantum query complexity.
Paper of the week: None. Project reports and presentations due next week.
- November 28
- Project presentations.
Schedule for the project presentations on November 28:
- Andrew Arnold. Improved sparsity testing of Boolean functions.
- Yi Zhang. Performance prediction and feature interaction detection by Fourier learning.
- Winnie Lam. CSPs and Boolean functions.
- Vijay Menon, Daniel Recoskie, and Chi Zhang. Learning addressing functions.
- Li Liu. Improved upper bound for worst case BLR in characteristic two.
- William Herring. Testing isomorphism for functions far from symmetric.
- Nathan Lindzey. A note on quasi-stability for homogeneous spaces.