CS 860, Section 2
Fall 2014
Friday, 9-11:50 in DC 3313
Piazza site
Office hours
Wednesday, 11-12 in DC 3119
Eric Blais

Course Description

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.

Course Outline


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.

Required background

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.

Course structure

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.


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.