📅 July 22—24, 2026 🌏 Sydney (Australia)
This 3-day intensive winter school will cover and discuss two fundamental results in computational complexity, which redefined the way we think about proofs, and led to a plethora of new research directions, results, and insights.
The IP=SPACE Theorem (the power of interaction)
The PCP Theorem (the power of randomization)
Register by July 15 (free, but required)
What are these? Computational complexity (a core area of theoretical computer science) is devoted to understanding which statements can be decided efficiently. The standard example is the class NP, the class of computational problems which might be hard to solve directly, but for which a proof can be easily checked (by a polynomial-time algorithm). Equivalently, one can view that as the class of decision problems with the following guarantees: there are two entities, a Prover (computationally unbounded, omniscient, but untrustworthy) and a Verifier (computationally bounded, polynomial-time) such that, when trying to decide whether some statement P is true; for every input x:
The Prover sends a short "proof" π(x) that P(x) is true to the Verifier, who reads and checks the proof in polynomial time (in |x|)
If P(x) is indeed true, then the Verifier can be convinced by some proof π(x)
If P(x) is not true, no matter what garbage "proof" the Prover sends, the Verifier will not be convinced
The above defines the class NP. Looking at this, one can think about generalizing it in several ways! What if Verifier and Prover could be randomized algorithms and only needed to be convinced with high probability? What if instead of just sending a purported proof π(x), the Prover started a discussion with the Verifier, interactively trying to convince them? What if instead of reading the whole proof π(x), the Verifier just looks at a very small fraction of it at random before deciding? Does that change anything? What can be "proven" this way?
The first one gives rise to the class MA (Merlin–Arthur): it is unknown whether MA=NP (does randomization alone change anything?). The second is the class IP (Interactive Proofs); while the third is the class PCP (Probabilistically Checkable Proofs). This Winter School will focus on the last two, and cover two incredible results: (1) every language which can be decided by algorithms using a polynomial amount of space (this is a huge class of languages: the class PSPACE) can be decided with an Interactive Proof! and (2) every language in NP can be decided looking at only a constant number of bits of the proof. Besides establishing these very deep theorems, one goal of the School will be to convey, at least partially, how mind-blowingly deep and surprising these two results are!
Who is it for? Everyone, from 3rd- or 4th-year undergraduate students with a solid algorithmic and/or mathematical background to graduate (HDR) students and interested academics. The Winter School will start with a "bootcamp" morning, to introduce the key concepts and necessary background to all. Attendees are expected to be familiar with discrete mathematics and discrete probability, and basics of computational complexity (computational models, Turing Machines, computational classes such as P and NP).
Important: we expect all participants to respect the values and standards described in the SoCG Code of Conduct.
Day 1 (Wednesday, July 22)
09:00–10:30: Bootcamp: Computational Complexity and a Few Good Tools (1)
10:30–10:45: Coffee break☕
10:45–12:15: Bootcamp: Computational Complexity and a Few Good Tools (2)
12:15-13:30: Lunch 🍽️ (not provided)
13:30–15:30: IP=PSPACE (1)
15:30–16:00: Coffee break☕
16:00–17:00: IP=PSPACE (2)
Day 2 (Thursday, July 23)
09:00–10:30: IP=PSPACE (3)
10:30–10:45: Coffee break☕
10:45–12:15: IP=PSPACE (4)
12:15-13:30: Lunch 🍽️ (not provided)
13:30–15:30: The PCP Theorem (1)
15:30–16:00: Coffee break☕
16:00–17:00: The PCP Theorem (2)
Day 3 (Friday, July 24)
09:00–10:30: The PCP Theorem (3)
10:30–10:45: Coffee break☕
10:45–12:15: The PCP Theorem (4)
12:15-13:30: Lunch 🍽️ (not provided)
13:30–15:30: The PCP Theorem (5)
15:30–16:00: Coffee break☕
16:00–17:00: Perspective, and Zero-Knowledge: What came and comes next?
The lectures will be given by Clément Canonne, Sasha Rubin, and Aditya Vikram Singh (School of Computer Science, The University of Sydney).