Lecturer Rahul Santhanam Degrees 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.

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

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.