CS 764, Spring 2014

Schedule of topics

Chapter and section references are to Arora and Barak's text, unless otherwise noted.

Preliminaries

For mathematical background material, skim through the appendix of Arora and Barak, as well as Chapter 0. Once you know what it contains, you can look up details as necessary. Some of the topics in the appendix will get lecture time, especially sections A.4 (finite fields), A.6 (polynomials) and perhaps A.5.3 (eigenvectors and -values). Details of coverage will depend on the actual background of attendees.

General schedule

To a first approximation, the course will divide into three parts:

May: Basics of computatonal complexity—models, resources and their relationships.
June: Some highlights of complexity—lower bounds, communication within computation, randomized computation, probabilistic analysis, etc.
July: Advanced topic(s). We will choose^† one or two areas and delve into them rather deeply.
(†: In other words, the instructor will decide, based in part on interests expressed by students.)

By necessity, we will omit some topics entirely and give short shrift to others. If you want to make sure some topic gets attention, please let the instructor know.

Week-by-week (all timings approximate)

Monday, May 5: Review of basic concepts: Turing machines, time complexity (Ch. 1)
Wednesday, Jan. 7: Space-bounded computation (Ch. 4).
"Hierarchies" arising from increasing time or space bounds. (§ 3.1)
Monday, May 12: Circuit complexity (§§ 6.1, 6.2).
Wednesday, May 14: Non-determinism (§§ 2.1–3). NP-complete problems.
Monday, May 19—official holiday: No lecture.
Wednesday, May 21 (an official Monday): Student discussion of exercises on finite fields.
Monday, May 26: Reductions and completeness: general defintions; examples.
Wednesday, May 28: Completeness for classes other than NP.
Space complexity: reachability in directed graphs. (Ch. 4)
Monday, June 2: Language complements, co-nondeterminism and alternation.
The Immerman/Szelepscényi theorem.
Wednesday, June 4: Alternation connects time and space complexity. (Ch. 5)
Friday, June 6 (in DC 3313): Probabilistic estimates and randomized computations: the classes BPP and R (A.2, parts of Ch. 7)
Monday, June 9: Randomized log-space (RL), and reachability in undirected graphs. (Ch. 7)
Wednesday, June 11: no class
Monday, June 16: Small-depth circuits and parallel computation (§6.7).
Parallel time corresponds to serial space.
Friday, June 20 (in DC 3313): Constant-depth circuits cannot compute parity, part I: approximating circuits with low-degree polynomials (§14.2)
Monday, June 23: Constant-depth circuits cannot compute parity, part II: low-degree polynomials cannot approximate parity (§14.2).
Other uses of the "approximation method"
Wednesdays, June 25 and July 2: IP=PSPACE. (Parts of Ch. 8)
Starting July 6: Derandomization and pseudo-random generators. Existence of very strong generators, based on lower bounds on circuit size. (Ch. 20)

Possible future topics

TBA: Hardness of approximation; "gap" theorems. (Ch. 11)
TBA: The PCP theorem and its relation to hardness of approximation. (Ch. 11)
TBA: Toward explicit pseudo-random generators: intro to expander graphs. (TBA—from Chs. 19, 20)
TBA: Explicit construction of pseudo-random generators. Improving small-space algorithms for reachability on undirected graphs. (Ch. 21)
TBA: Proving the PCP theorems: amplifying rejection probabilities. (Ch. 22)

End of term

July 28: Project presentations.
July 30: Project presentations.