Lecturer	Rahul Santhanam
Degrees	Schedule C1 (CS&P) — Computer Science and Philosophy Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science Michaelmas Term — MSc in Advanced Computer Science
Term	Michaelmas Term 2022  (20 lectures)

Overview

The course will interest students who are interested in the foundational aspects of the theory of computation. It will discuss fundamental open problems in computational complexity theory, such as the P vs NP prob- lem, as well as approaches and barriers to solving these problems. A wide range of techniques will be considered - combinatorial, algebraic, logical, algorithmic - and applied to uniform as well as to non-uniform computational models. Along the way we will explore other exciting topics such as the theory of pseudorandomness and the relevance of meta-mathematical results such as Godel's Theorem to complexity theory.

(Scheduling note: The lecture on 04 Nov is cancelled owing to ill-health, and might be rescheduled on a future Friday. The lecture on 07 Nov will be given by Jan Pich.)

Learning outcomes

1. Understand the fundamental open questions in computational complexity and their significance
2. Analyse relationships between complexity classes
3. Understand and apply various combinatorial, algebraic and logical techniques for proving complexity lower bounds
4. Appreciate why complexity lower bounds are hard to prove, informally and through the formulation of formal mathematical barriers
5. Exploit relationships between algorithms and lower bounds, in the context of hardness-randomness tradeoffs and the algorithmic method

Prerequisites

1. A strong background in discrete mathematics, including combinatorics, discrete probability, graph theory and basic abstract algebra, as well as in propositional logic

2. Experience with mathematical proofs, especially in the context of computation

3. Some previous exposure to complexity theory. Part A/Part B Computational Complexity course or equivalent is preferred, but not essential

Synopsis

1. Basic complexity background and Results based on Simulation and Diagonalization [~5 lectures]: Time, space, non-determinism, randomness, non-uniformity and alternation as resources. Hierarchy theorems for time, space and non-determinism. Simulation results for time vs space and time vs non-determinism. Reducibility and completeness. The P vs NP problem and its significance. The Karp-Lipton theorem and Kannan's theorem. Time-space tradeoffs for Satisfiability.
2. Lower bounds for Weak Models [~6 lectures]: Constant-depth circuits and the random restriction method. The polynomial method. Neciporuk's method and formula lower bounds. Gate elimination.
3. Hardness versus Randomness [~3 lectures]: Hardness amplification. The Nisan-Wigderson generator. Cryptographic generators.
4. Barriers to Lower Bounds [~3 lectures]: Relativization. Natural proofs.
5. Beyond the Barriers [~3 lectures]: Hardness magnification. The algorithmic method.

Reading list

1. Written lecture notes for the course (which will lag slightly behind the lectures)

2. The book "Computational Complexity: A Modern Approach" by Arora and Barak: Link

3. Ryan O'Donnell's lecture notes for "Graduate Computational Complexity Theory": Link

4. Dieter van Melkebeek's lecture notes for "Complexity Theory": Link

5. Eric Allender's Complexity Theory lecture notes: Link

6. Luca Trevisan's lecture notes on Computational Complexity: Link

7. Research papers, including the Razborov-Rudich paper on "Natural Proofs", the Nisan-Wigderson paper on "Hardness vs

Randomness" and Williams' paper on "Non-Uniform ACC Circuit Lower Bounds"

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.