Abstract: Error-correcting codes can be used to make data robust against adversarial corruption. It has long been known that special types of codes can be used to similarly robustify *computation* against such adversarial corruption, leading to many types of probabilistic proof-systems such as PCPs, IOPs etc. In this talk I will discuss a recent line of work that shows that one can actually use general purpose codes for proof-system design. Such abstractions lead to new protocols that are highly efficient and yet conceptually very simple.

Abstract: Expansion in graphs very often appears in constructions that require resilience to errors. Many error-correcting codes rely on expander graphs, as do PCP constructions. In recent years new notions of expansion are studied, which are called "high dimensional expansion". I will give a gentle introduction to high dimensional expansion and describe how they appear in locally testable codes and in PCPs.

Abstract: How close to the code is a random word liable to be? We show that, in MDS codes with reasonably large block and message lengths, the vast majority of words are much closer to the code than the code's covering radius demands that they be. More precisely, we show that the proportion of Hamming space collectively covered by the radius-𝑧 Hamming balls can be made to decay more slowly than 𝑛ᶜ / 𝑞 does—for c an arbitrarily large integer—in the limit of large 𝑛. Here, the ball radius 𝑧's absolute distance from the code's covering radius itself grows arbitrarily large in 𝑛. Our results disprove the capacity conjecture of Ben-Sasson, Carmon, Ishai, Kopparty and Saraf (J. ACM '23). We discuss applications to SNARKs. This work is joint with Angus Gruen.

Abstract: Reed-Solomon (RS) codes were recently shown to exhibit an intriguing proximity gap phenomenon. Specifically, given a collection of strings with some algebraic structure (such as belonging to a line or affine space), either all of them are δ-close to RS codewords, or most of them are δ-far from the code. Here δ is the proximity parameter which can be taken to be the Johnson radius 1-√R of the RS code (R being the code rate), matching its best known list-decodability. Proving proximity gaps beyond the Johnson radius, and in particular approaching 1-R (which is best possible), has been posed multiple times as a challenge with significant practical consequences to the efficiency of SNARKs. In this work, we show that most codes in the literature that have been shown to achieve list-decoding capacity, i.e., are list-decodable up to a fraction of errors approaching 1-R, exhibit proximity gaps for δ<1-R. This includes folded Reed-Solomon codes, univariate multiplicity codes, random linear codes, and random Reed-Solomon codes.

Abstract: Interactive Oracle Proofs (IOPs) are a central tool in the construction of efficient succinct arguments. The efficiency of almost all known IOP constructions is determined largely by two shared underlying components: (1) a linear code C and (2) an Interactive Oracle Proof of Proximity (IOPP) which convinces the verifier that the IOP prover’s messages are close to C. In this talk we will present a new framework that enables modular construction of IOPPs from simple building blocks. We will then discuss one such IOPP construction that proves proximity to a large class of linear-time encodable codes with optimal prover time and verifier query complexity.