## Methods and Tools in the Theory of Computing

### Module aims

Can we find solutions of problems as quickly as we can identify the correctness of their solutions once given to us? Does every valid formula have short proofs? Are there functions that are easy to compute but hard to invert? These and similar questions are the fundamental hardness questions of computer science, which are central to both theory and practice of computing. This module focuses on elementary tools, methods and results relating to these questions: the combinatorial method, through circuit complexity, the algebraic approach, through algebraic complexity, and the logical approach, through proof-complexity.

### Learning outcomes

Upon successful completion of this module you will be able to:
- Prove fundamental properties of Boolean circuits and their size-complexity.
- Apply the polynomial method to analyse the complexity of algebraic computation.
- Estimate the Boolean circuit size required to compute certain functions using elementary probabilistic techniques.
- Analyse the proof-complexity of certain propositional proof systems.

### Module syllabus

Models:
- The Boolean Circuit model
- Shannon lower bounds: most Boolean functions require large circuits
- Connections between circuits and the classes P, NP and Turing machines
- Propositional proof systems
- Cook's programme to seprate P from NP
- Algebraic circuit model
Tools:
- The random restriction method & switching lemmas
- Constant depth circuit lower bounds
- Resolution lower bounds for the Pigeonhole Principle
- The Approximation method: monotone circuits lower bounds
- The polynomial method: lower bounds against algebraic computation
- Lower bounds against constant depth circuits with counting gates

### Teaching methods

The material will be taught through traditional lectures and tutorial sessions. You will be set formative unassessed exercises designed to reinforce the material as it is taught. Approximately half of these exercises will be discussed in class; the remainder are intended for you to use for self-study.

An online service will be used as a discussion forum for the module.

### Assessments

There will be one written coursework that contributes 20% of the mark for the module. There will be a final written exam, which counts for the remaining 80% of the marks.

Written and verbal feedback will be given on the assessed coursework.