Analytic techniques have become influential in many areas of theoretical computer science. This course will survey some of the most broadly applicable of these techniques and their most important applications. Techniques to be covered include discrete Fourier analysis and approximation theory. Application domains include PAC learning, quantum computing, and communication complexity.
There are no formal prerequisites for this course. However, substantial mathematical maturity will be expected, as will knowledge of basic probability theory, induction, asymptotic notation, modular arithmetic, and the notion of NP-completeness (these topics will be reviewed in lecture, but quickly). If you have not previously taken an algorithms or theory of computation course, you will likely be unprepared.
The course reference is a draft monograph written by the instructor that is available on Canvas.
Grades in the course will be based on participation (comments on the reading), problem sets, and a final project. Each component will count for 1/3 of the grade. Information about the final project will be provided later in the semester.
After class or by appointment.
Below is the highly tentative schedule for the course. I will modify it as the semester progresses. Topics and readings will not become "official" until the date of lecture.
|1||8/24||Course overview; introduction to approximate degree and its applications: quantum computing, query complexity, communication complexity||No reading.|
|2||8/29||Fourier Analysis of Boolean Functions||Section 1 of Bun and Thaler. Sections 1.1 - 1.4 of Analysis of Boolean Functions by Ryan O'Donnell|
|3||8/31||Introduction to Approximate Degree. Upper bound for OR.||Section 2 of Bun and Thaler|
|4||9/6||Lower bound for OR.||Sections 3.1-3.3 of Bun and Thaler|
|5||9/7||Introduction to query complexity. The polynomial method in query complexity. Error reduction for randomized query complexity and approximate degree.||Sections 5.0 and 5.1 of Bun and Thaler|
|6||9/12||Approximate degree of symmetric functions. Threshold degree lower bound for Parity.||Section 4.1 of Bun and Thaler, followed by Sections 3.4 and 3.5. Optional reading: Section 3 of Buhrman and de Wolf's survey on query complexity and related topics|
|7||9/14||Threshold degree upper and lower bounds for the Minsky-Papert CNF||Section 5.3 of Bun and Thaler|
|8||9/19||Application: PAC learning||Begin Section 11.2 of Bun and Thaler|
|9||9/21||Application: Agnostic learning||Finish Section 11.2 of Bun and Thaler|
|10||9/26||Introduction to linear programming and duality||Section 12.1 of Vazarani's book|
|11||9/28||The method of dual polynomials for lower bounding approximate degree||Section 6.0 of Bun and Thaler|
|12||10/3||Application: Secret sharing schemes via dual polynomials||Section 11.1 of Bun and Thaler|
|N/A||10/5||Dual block composition, approximate degree lower bound for the AND-OR tree||Sections 7.0 and 7.1 of Bun and Thaler|
|13||10/10||Campus holiday, no class||No reading|
|14||10/12||Hardness amplification results via dual block composition||Section 7.2 of Bun and Thaler|
|15||10/17||Introduction to communication complexity||Section 10.2 of Bun and Thaler|
|16||10/19||Query-to-communication lifting theorems||Sections 10.0, 10.1, and 10.3 of Bun and Thaler|
|17||10/24||Begin the pattern matrix method for communication lower bounds||Sections 10.4.0-10.4.1 of Bun and Thaler|
|18||10/31||Finish the pattern matrix method for communication lower bounds||Sections 10.4.0-10.4.2 of Bun and Thaler|
|19||11/2||Applications in communication and circuit complexity, Part 1||Reading TBD|
|20||11/7||Applications in communication and circuit complexity, Part 2||Reading TBD|
|21||11/9||Applications in communication and circuit complexity, Part 3||Reading TBD|