Theory of computation 2026

Theory of Computation

Class Telegram group: Join the class group

Lectures and seminars

No.	Date	Lecture	Contents and principal results	Lecture notes	Seminar notes
1	11 September	Computational models and resource bounds	Multitape Turing machines and efficient universal simulation. Time and space complexity; DTIME, DSPACE, P, PSPACE, and EXP. Time- and space-constructible bounds.	Lecture notes
2		Nondeterminism, NP, and reductions	Nondeterministic machines and polynomial-time verifiers; proof of their equivalence. Polynomial-time many-one reductions, NP-hardness, and NP-completeness.
3		The Cook–Levin theorem	Tableau proof that Boolean satisfiability is NP-complete: encoding configurations, local transitions, the initial configuration, and acceptance.
4		Time and space hierarchy theorems	Diagonalization and universal simulation. Full proofs of the deterministic time hierarchy theorem and the deterministic space hierarchy theorem.
5		Space complexity and Savitch's theorem	Configuration graphs and STCON as an NL-complete problem. Recursive reachability and the proof of NSPACE(s) ⊆ DSPACE(s²); in particular, NPSPACE = PSPACE.
6		The Immerman–Szelepcsényi theorem	Inductive counting of reachable configurations and the complete proof that nondeterministic space is closed under complement; in particular, NL = coNL.
7		PSPACE-completeness	Quantified Boolean formulas and recursive evaluation. Complete proof that TQBF is PSPACE-complete via polynomial-space configuration reachability; applications to games and planning.
8		Boolean circuits and nonuniformity	Circuit families, size, and depth. Simulation of polynomial-time machines by polynomial-size circuits; P ⊆ P/poly and the characterization of P/poly by polynomial advice.
9		Circuit size and parallel computation	The counting lower bound for Boolean circuits. Uniformity; the classes AC and NC; elementary depth lower bounds, the locality of NC⁰, and a constant-depth construction for binary addition.
10		The polynomial hierarchy	The classes Σₖᴾ and Πₖᴾ and their quantified-predicate characterizations. Complete quantified-circuit problems, collapse of the hierarchy, and PH ⊆ PSPACE.
11		Randomized computation	Probabilistic machines and the classes RP, coRP, ZPP, and BPP. Error amplification, ZPP = RP ∩ coRP, and the probabilistic proof that BPP ⊆ P/poly.
12		The Sipser–Gács–Lautemann theorem	Amplification to exponentially small error, translations of accepting random strings, and the covering lemma. Full proof that BPP ⊆ Σ₂ᴾ ∩ Π₂ᴾ.

Lecturers

Role	Lecturer	Contact	Office hours
Lecturer	Subin Pulari	Telegram: @spulari Email: spulari@hse.ru	Monday–Friday, by appointment via Telegram or email
Seminar lecturer	Yaroslav Ivanashev	Telegram: @ivanashev

References

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach.
• Michael Sipser, Introduction to the Theory of Computation.

Evaluation scheme

The course has one midterm assessment and one end-term assessment. Each assessment consists of one colloquium and one written examination.

Let C_mid and C_end denote the two colloquium scores, and let E_mid and E_end denote the two examination scores. The aggregate scores are

C = (C_mid + C_end)/2,     E = (E_mid + E_end)/2.

The final course score is

Final score = 0.6 C + 0.4 E