CSCI 5170: Computational Complexity

The Chinese University of Hong Kong, Spring 2016

• Lectures Tue 2:30-5:15 in ERB 804
• Instructor Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926
• Office hours Fri 2-4 (or by appointment)

Recent Announcements

• Apr 7 The project presentations will be held in class on Apr 19. The total time for each group is 15 minutes. You should aim for a 12 minute presentation to leave time for questions. Please turn in your report by Apr 26.
• Mar 30 Homework 3 is out. Please hand in the assignment in class on Apr 12.
• Mar 30 I made some minor corrections to the Lecture 11 notes.

Course Description

Computational complexity is the mathematical study of computational efficiency. It is concerned with identifying efficient models of computation and understanding their power, their limitations, and their interrelationships.

In this offering we will emphasize models that come up in modern information processing applications (such as cryptographic protocols, combinatorial optimization, "big data" computations, machine learning). The methodology is mathematically rigorous in the style of the theory of computing.

This course is a must for serious students of the theory of computing. It is also relevant to any discipline where computation plays a role, including cryptography, optimization, learning, data analysis, information theory, and combinatorics.

Lectures

	date	topic	notes
1	Jan 12	Circuits: Decision trees, disjunctive normal form	pdf
2	Jan 19	Parallel computation: Small depth circuits	pdf
3	Jan 26	Sequential computation: Branching programs	pdf
4	Feb 2	Monotone circuits	pdf
	Feb 9	Lunar New Year holiday
5	Feb 16	Algorithms: Deterministic, nondeterministic, randomized	pdf
6	Feb 23	Average-case complexity and one-way functions	pdf
7	Mar 1	Pseudorandom generators	pdf
8	Mar 8	Sublinear-time algorithms and quantum algorithms	pdf
9	Mar 15	Proofs: Randomness and interaction in proof systems	pdf
10	Mar 22	Refutations and statistical zero-knowledge	pdf
11	Mar 29	PCPs and approximation algorithms	pdf
12	Apr 5	Proof of the PCP theorem	pdf
13	Apr 12	Pseudorandom functions, learning, and natural proofs	pdf
	Apr 19	Project presentations

Course Information

• Prerequisites There are no formal prerequisites, but knowledge of algorithms (at the level of CSCI3160) and computability (at the level of CSCI3130) is helpful. Familiarity with discrete mathematics and probability will be assumed. If you are not sure you know these topics please talk to me.
• Grading Your grade will be determined from 3 homeworks (30%), a take-home midterm exam (30%), and a final project (40%). Homeworks will be issued throughout the semester.
• Final project For your final project you will be expected to do a small research project or some independent reading. You will present your work class and write a short report.

References

Notes will be provided for every lecture. The main reference is

• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2008. [CUHK e-copy]

Most of the material can be found in this book, although our emphasis and presentation may be different. The following two books are also recommended:

• Oded Goldreich. Computational complexity: A conceptual perspective. Cambridge University Press, 2008.
• Stasys Jukna. Boolean function complexity: Advances and frontiers. Springer-Verlag, 2012. [CUHK e-copy]