Foundations of Probabilistic Proofs

A brief overview of the structure and content of the course. We present theoretical and practical motivations for the material in the course.

We introduce interactive proofs (IPs), which extend the notion of a mathematical proof by allowing the verifier checking the statement to use randomness and exchange messages with a prover. We present an IP for the language of graph non-isomorphism (GNI), which is not known to be in BPP. We show that every language having an IP is contained in PSPACE. Finally, we discuss strategies for error reduction for an IP.

We show that IPs capture all languages in P^{#P}, a rich complexity class that contains NP and coNP (and is believed to be much larger than that). We introduce the concept of arithmetization, which translates logical satisfiability to algebraic constraints. We present the sumcheck protocol, a powerful tool that allows to very efficiently check the sum of a low-degree polynomial over a product domain. Along the way, we discuss the Polynomial Identity Lemma, a basic property of low-degree polynomials.

We show that every language in PSPACE has an IP. We discuss how to arithmetize the PSPACE-complete language TQBF (true fully quantified boolean formulas), and then describe Shamir's protocol (an IP for the resulting algebraic problem). We show that TQBF is PSPACE-complete.

So far we have studied IPs without considering the complexity of the honest prover. In this lecture we introduce doubly-efficient IPs, which are IPs in which the honest prover runs in polynomial time. The motivation is delegation of computation: in a doubly-efficient IP for a language the verifier should be "cheaper" than the decider of the language (without the prover's help). We describe the (bare-bones) GKR protocol, a doubly-efficient IP for bounded-depth circuit computations.

We introduce zero knowledge IPs, which enable proving that a statement is true without revealing any information (beyond the fact that the statement is true). We discuss an IP for graph isomorphism (GI), and show that it is zero knowledge against honest verifiers and also malicious verifiers. We discuss limitations of zero-knowledge IPs, leading to a surprising connection between the zero-knowledge IP for GI and the IP for GNI discussed in Lecture 1. Finally, we discuss the GMW protocol for graph 3-colorability, which leads to *computational* zero knowledge IPs for every language in NP.

We introduce probabilistically checkable proofs (PCPs), a model of probabilistic proof wherein the prover sends a (possibly large) proof string which the verifier is able to query at arbitrary positions. We show that PCPs capture all languages in IP (and thus in PSPACE) and tease additional capabilities of PCPs such as delegation of general nondeterministic computations. Finally, we describe Killian’s protocol, a fundamental approach to achieve succinct arguments by combining a PCP and a collision-resistant hash function (a simple cryptographic primitive).

We introduce proximity testing: the problem of distinguishing, via few queries to a function, whether the function belongs to a certain function class or is far from (all functions in) that class. Property testing plays a key role in achieving small query complexity for PCPs. We discuss simple examples of proximity tests, and then introduce and analyze the Blum-Ruby-Rubinfeld test for linear functions. Moreover, we discuss local correction for linear functions, which applies to functions that are close to linear. Finally, we sketch an improved analysis of the BLR test that leverages Fourier analysis.

We describe a PCP for NP with exponential proof length and constant query complexity. This is achieved via an elegant and powerful approach: a compiler that, leveraging linearity testing and local correction for linear functions (both from Lecture 7), transforms any linear PCP into a corresponding (standard) PCP. Linear PCPs are a variant of PCPs where the verifier makes algebraic (in this case, linear) queries to the PCP string. We describe how to construct linear PCPs for NP with polynomial (and linear) proof length and constant query complexity.

We study proximity testing for (evaluations of) low-degree polynomials. First we describe a simple proximity test for univariate low-degree polynomials, which is essentially optimal. Then we explain how the simple test extends to the multivariate case, but yields large query complexity. This issue is overcome by the Rubinfeld-Sudan test, which achieves a query complexity that is independent of the number of variables. We analyze the test and discuss low-degree testing in general.

We describe a PCP for NP with polynomial proof length and polylogarithmic query complexity. We follow an approach that is analogous to the one we used in Lecture 8: we combine a low-degree test (which we studied in Lecture 9) and a low-degree PCP (which we construct in this lecture). Along the way we use the sumcheck protocol viewed as a PCP (by unrolling the IP interaction).

We prove that PCP=NEXP by describing a PCP for OSAT, a succinct variant of the SAT problem that is NEXP-complete. We show how to arithmetize an OSAT instance, which leads to the problem of zero-on-subcube testing for polynomials. We show a low-degree PCP for this problem, which we combine with a low-degree test. We thus see a first example of sublinear verification for PCPs: a PCP verifier whose time complexity is asymptotically less (indeed, exponentially less) than the time complexity of the (nondeterministic) decider of the language.

We show that PCPs enable delegation of general nondeterministic computations: we prove that every language in NTIME[T] has a PCP with prover time poly(T) and verifier time poly(n,logT). Constructing the PCP involves an efficient "scale down" of the PCP for NEXP, which demands a number of delicate changes, including a different NTIME-complete problem (IOSAT) and a different arithmetization via low-degree multivariate polynomials.

We introduce interactive oracle proofs (IOPs), a model of probabilistic proof that simultaneously generalizes the IP model and PCP model. We show that IOPs capture the same languages as PCPs (i.e. NEXP). We revisit a PCP for NP and show that interaction can significantly reduce the proof length. Finally, we discuss how IOPs lead to succinct arguments: we describe the (interactive) BCS protocol, an analogue to Kilian’s protocol that achieves succinct arguments by combining an IOP and a collision-resistant hash function.

We explore how IOPs can further reduce proof length compared to PCPs. We describe an IOP for NP with linear proof length and logarithmic query complexity. Specifically, we target a popular NP-complete problem known as rank-1 constraint satisfiability (R1CS). We encode information using univariate polynomials, and accordingly discuss a univariate analogue of the sumcheck protocol. In turn, this motivates the study of IOPs of proximity for the Reed–Solomon code, which we study in the next lecture.

We study the problem of testing proximity to the Reed–Solomon code in the IOP model. We motivate and discuss the FRI protocol, an IOP for proximity for Reed–Solomon codes with linear proof length and logarithmic query complexity. We also present simple lower bounds on the soundness of the FRI protocol.

This lecture concludes the analysis of FRI, by upper bounding the soundness error of the protocol.

We describe an IOP for (nondeterministic) machine computations with linear proof length and polylogarithmic verifier time. This provides a highly efficient approach to delegate computations in the IOP model. First, we construct an IOP for automata computations. This IOP uses a zero-on-subset subprotocol as a building block, and encodes automata computations via the language of rational constraints. Then, to handle general machine computations, we show how to ensure memory consistency via permutation checks.

We consider the problem of achieving sublinear verification for general computation. We introduce holographic IOPs, which involve a preprocessing step (run by a trusted indexer) for the non-input dependent part of the computation to be proven. We discuss definitions of holographic IPs, PCPs, and IOPs, and revisit existing protocols to show how they can introduce holography. Finally, we show that holographic proof systems, after a compilation akin to Micali and BCS, lead to preprocessing succinct arguments.

We start proving the PCP Theorem, a seminal result stating that every language in NP has a PCP with polynomial proof length and constant query complexity. The high-level strategy involves proof composition, a powerful paradigm that constructs a PCP from an outer PCP and an inner PCP. Roughly, the resulting PCP inherits the proof length of the outer PCP and the query complexity of the inner PCP. We introduce notions under which proof composition works: robustness and proofs of proximity. Then we prove the PCP Theorem assuming the existence of two ingredients: (1) a robust outer PCP of proximity (PCPP) with polynomial proof length and logarithmic query complexity; and (2) an inner PCPP with exponential proof length and constant query complexity. We also discuss proof composition for IOPs.

We show how to transform a PCP into a robust PCP, in order to construct the first building block for the PCP Theorem. A robust PCP is one satisfying a stronger notion of soundness: with high probability, a local view is far from any local view that would make the PCP verifier accept. The transformation involves two steps: query bundling and robustification. Query bundling reduces query complexity to constant, at the expense of alphabet size. Robustification achieves constant robustness, at the expense of query complexity.

We study PCPs of Proximity (PCPPs), which are PCPs wherein the verifier is given oracle access to a purported witness, and the soundness condition states that the verifier rejects (with high probability) if the given witness is far (in Hamming distance) from the set of valid witnesses. Then we construct PCPPs by modifying two PCPs that we previously constructed, by using a local decoder. This lecture concludes the proof of the PCP Theorem.

The IP for graph non-isomorphism in Lecture 1 is an example of a private-coin IP. We show that private coins do not significantly help the IP verifier: any private-coin IP can be transformed into a public-coin IP by adding a single additional round. This reduction introduces a completeness error, which then we show how to remove.

We discuss the limitations of IPs with small communication complexity. First, we show that any IP can be decided by a deterministic machine in time exponential in the two-way communication complexity. Next, we show that any public-coin IP can be decided by a probabilistic machine in time exponential in prover-to-verifier communication. Finally, we discuss extensions of this second result to private-coin IPs.

We study limitations of PCPs and IOPs. We show that one-query PCPs for SAT (with small alphabet) would contradict RETH, and that two-query PCPs over a binary alphabet are trivial. We then consider limitations on soundness for PCPs, introduce the sliding scale conjecture, and motivate its statement. Finally, we investigate analogous questions for IOPs.

We discuss parallel repetition, a method to reduce the soundness error of a proof system. Perhaps surprisingly, the behavior of parallel repetition is strikingly drifferent across different models of probabilistic proof. We see this by considering parallel repetition for IPs, MIPs, and PCPs.

In prior lectures we discussed cryptographic applications of PCPs and IOPs, as tools towards delegation of computation. In this lecture we discuss applications to hardness of approximation. PCPs can be used to show that NP-hard problems are not only hard to solve, but also hard to approximate within certain factors.