Computational Complexity 2

Published

18 October 2026

Passport

  • Status of the title. The official 01.03.02 curriculum for the 2025 intake has no separate discipline titled β€œComputational Complexity 2”.
  • Closest confirmed discipline. Semester VI has an elective course β€œComputational Complexity: Additional Chapters”: 45 hours, 1 credit, 30 contact hours (15 lecture hours, 15 seminar hours) and 15 hours of independent work.
  • Department and lecturer. In the public curriculum the specialization is discrete mathematics; no lecturer is given for this version.
  • Final assessment. For the elective course, the form of assessment cannot be identified unambiguously from the extracted fragment of the curriculum; check the current curriculum for your group.

Contents

No primary program was found for the title β€œComputational Complexity 2”. However, the full plan of the related elective course β€œComputational Complexity: Additional Chapters”, semester VI, version of February 1, 2024, is published. It does not stand in for a separate discipline that does not exist in the curriculum, but it is given here in full as the available material:

  1. Interactive protocols, the classes \(dIP\) and \(IP\), completeness and soundness, the examples of graph isomorphism and quadratic non-residues; the inclusion \(IP\subseteq PSPACE\).
  2. Public coins, Arthur–Merlin games, the classes \(AM\) and \(MA\), pairwise independent hash functions and the Goldwasser–Sipser protocol.
  3. Shamir’s theorem \(IP=PSPACE\): arithmetization, protocols for \(\#SAT\) and \(TQBF\).
  4. Perfect, statistical and computational zero knowledge; the classes \(PZK\), \(SZK\), \(CZK\) and the example of graph isomorphism.
  5. One-way functions, commitment schemes, zero knowledge for 3-coloring, the ideas behind the inclusions \(NP\subseteq CZK\) and \(IP\subseteq CZK\).
  6. Probabilistically checkable proofs, the class \(PCP\), approximation of NP-complete problems, the PCP theorem and Khot’s conjecture.
  7. Multi-prover protocols, the class \(MIP\) and the equality \(MIP=MIP2=PCP(poly,poly)=NEXP\).
  8. Rational interactive proofs, the classes \(FRMA\), \(DRMA\), \(RIP\), the counting hierarchy.
  9. Complexity of total search problems: \(TFNP\), the classes \(PLS\), \(PPP\), \(PPA\), \(PPAD\) and complete problems.

The program also states that materials, assignments, partial solutions, individual homework assignments and a practice version were to be published in a Telegram channel and a shared folder. The grading section of the document says only β€œto be added”: no numerical grading scheme has been published.

Reading list in the 2024 program

D. V. Musatov, Computational Complexity: Classics and Modern Times (draft); S. Arora, B. Barak, Computational Complexity: A Modern Approach; O. Goldreich, Foundations of Cryptography, Vol. I and Computational Complexity: A Conceptual Perspective; C. Moore, S. Mertens, The Nature of Computation; J. Katz, Notes on Complexity Theory; C. Papadimitriou, Computational Complexity. The online resources named are the Complexity Zoo, Dick Lipton’s blog, Shtetl-Optimized, the Computational Complexity Blog and question-and-answer sites on theoretical computer science.

Grading

No public grading scheme was found.

Sources and currency

01.03.02 curriculum, 2025 intake and program of the related course, 2024.