VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Mathematical Aspects of Interactive Proof Systems
Last Updated: 2026-06-01 11:31:23
Abstract
This seminar explores how tools from graph theory (notably expander graphs), probability, and algebra arise in interactive proofs—a framework where a verifier interacts with a prover to check a statement’s validity. We’ll introduce interactive proofs, cover the PCP theorem and its graph-theoretic proof, then touch on recent developments such as MIP* = RE and its implications for operator algebras.
Content
An interactive proof system is a framework from theoretical computer science involving a dialogue between a prover, who holds a proof, and a verifier, who wants to be convinced of its validity. Traditional mathematical proofs are static: the prover writes a complete argument, and the verifier reads it in full—both steps typically requiring similar computational effort. By contrast, interactive proofs allow a resource-limited verifier to interact with a powerful prover through a carefully designed protocol. A landmark result in this area is the PCP (Probabilistically Checkable Proofs) theorem, which shows that a verifier can be convinced of a proof’s correctness by reading only a constant number of randomly chosen symbols from it—provided the proof is suitably encoded. Interactive proofs also underpin powerful notions such as zero-knowledge proofs and multi-prover systems, with far-reaching applications in cryptography and complexity theory. Perhaps more surprisingly, interactive proof systems have recently emerged as a powerful tool in pure mathematics. For instance, quantum interactive protocols—such as those involved in the result MIP* = RE—have led to breakthroughs in areas as distant as operator algebras and noncommutative geometry. In this student seminar, we will explore the mathematical side of interactive proof systems along three axes: (1) an introduction to the general model and classical protocols (e.g. zero-knowledge proofs, sumcheck), (2) a proof of the PCP theorem using graph-theoretic tools, notably expander graphs, and (3) recent advances involving quantum protocols, focusing on the result MIP* = RE and its unexpected implications in operator algebras, including the refutation of Connes’ embedding conjecture.
General Information
- Language
- English
- Levels
- BSC , MSC
Examination
- Type
- ungraded semester performance
Registration & Places
- Signup End
- 06.09.2025
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| seminar | Mathematical Aspects of Interactive Proof Systems (tbd) |
|
2 h weekly |
Offered In
-
-
Seminare (ZUR BEACHTUNG: Damit die Zuteilung der verfügbaren Seminarplätze sich nicht primär auf den Zeitpunkt des Einschreibens in die Warteliste stützen muss, haben fast alle Mathematik-Seminare ein spezielles Auswahlverfahren. Eine direkte Belegung in myStudies ist nicht möglich, alle kommen zuerst auf die Warteliste. Ausserdem gilt: Die Auswahl an Mathematik-Seminaren wird auf 1 Seminar pro Semester beschränkt. Beachten Sie auch die Lerneinheit 401-0002-99L Generic Seminar - Second Priority / Third Priority.)
-
-
-
-
Seminare (ZUR BEACHTUNG: Damit die Zuteilung der verfügbaren Seminarplätze sich nicht primär auf den Zeitpunkt des Einschreibens in die Warteliste stützen muss, haben fast alle Mathematik-Seminare ein spezielles Auswahlverfahren. Eine direkte Belegung in myStudies ist dann nicht möglich, alle kommen zuerst auf die Warteliste. Ausserdem gilt: Die Auswahl an Mathematik-Seminaren wird auf 1 Seminar pro Semester beschränkt. Beachten Sie auch die Lerneinheit 401-0002-99L Generic Seminar - Second Priority / Third Priority.)
-
-