Theory of computation 2026

Theory of Computation

Lectures and seminars

Lecture	Contents	Lecture notes	Seminar notes
1	Computational models and resource bounds. Multitape Turing machines; configurations; time and space complexity; DTIME and DSPACE; P, PSPACE, and EXP; machine-model robustness; efficient universal simulation in O(T log T) time; time- and space-constructible bounds.
2	Nondeterminism, NP, and reductions. Nondeterministic computation; polynomial-time verifiers and certificates; equivalence of the two definitions of NP; polynomial-time many-one reductions; NP-hardness and NP-completeness; bounded nondeterministic machine acceptance.
3	The Cook–Levin theorem. Computation tableaux; Boolean encoding of configurations; start, transition, and acceptance constraints; local consistency; the local-to-global argument; polynomial-size construction; SAT is NP-complete.
4	Time and space hierarchy theorems. Diagonalization; padded machine descriptions; universal simulation; deterministic time hierarchy; deterministic space hierarchy; constructibility; strict separations between resource-bounded classes.
5	Space complexity and Savitch's theorem. Configuration graphs; logarithmic space; directed s–t connectivity; log-space reductions; STCON is NL-complete; recursive reachability; Savitch's theorem NSPACE(s) ⊆ DSPACE(s²); NPSPACE = PSPACE.
6	The Immerman–Szelepcsényi theorem. Nondeterministic space and complementation; reachability layers; inductive counting; certification of nonreachability; NL = coNL; closure of nondeterministic space under complement.
7	PSPACE-completeness. Quantified Boolean formulas; recursive QBF evaluation; TQBF ∈ PSPACE; succinct configuration reachability; universal-selector compression; PSPACE-hardness of TQBF; games and succinct planning.
8	Boolean circuits and nonuniformity. Boolean circuits; circuit size and depth; circuit families; P/poly; simulation of polynomial-time machines by polynomial-size circuits; nonuniform computation; polynomial advice; equivalence between polynomial advice and polynomial-size circuit families.
9	Circuit size and parallel computation. Shannon's counting argument; existence and abundance of hard Boolean functions; uniformity; NC^k and AC^k; bounded-fan-in depth lower bounds; locality of NC^0; constant-depth circuits for binary addition.
10	The polynomial hierarchy. Alternating quantified-predicate characterizations; Σ_k^P and Π_k^P; quantified-circuit complete problems; complementation; collapse of the polynomial hierarchy; PH ⊆ PSPACE.
11	Randomized computation. Probabilistic Turing machines; RP, coRP, ZPP, and BPP; one-sided and two-sided error amplification; ZPP = RP ∩ coRP; Adleman's theorem BPP ⊆ P/poly.
12	The Sipser–Gács–Lautemann theorem. Amplification to exponentially small error; dense and sparse accepting sets; translations of the Boolean cube; covering lemma and the probabilistic method; quantified covering characterization; BPP ⊆ Σ_2^P ∩ Π_2^P.
13	Communication complexity. Deterministic two-party protocols; protocol trees and transcripts; communication matrices; combinatorial rectangles; rectangle lower bounds; deterministic complexity of EQUALITY; public-coin fingerprinting; one-way communication; the INDEX lower bound.
14	Streaming algorithms and sketches. One-pass streaming and frequency vectors; point queries; pairwise-independent hashing; Count–Min Sketch; collision analysis and confidence amplification; fixed-query and simultaneous guarantees; sketch space complexity; communication reductions; INDEX-based streaming-space lower bounds.

Lecturers

Role	Lecturer
Lecturer	Subin Pulari
Seminar lecturer	Yaroslav Ivanashev

Evaluation policy

The course evaluation consists of two colloquia and two examinations:

• Colloquium 1
• Colloquium 2
• Midterm examination
• Final examination

The final grade is calculated as follows:

• Colloquia: 60% — average of the two colloquium grades.
• Examinations: 40% — average of the midterm and final examination grades.

Final grade = 0.6 × (average colloquium grade) + 0.4 × (average examination grade).