Fast proximity tests for algebraic linear codes

Most constructions of probabilistically checkable proofs (as well as their interactive variants) involve a proximity testing problem for linear codes. Specifically, the goal is to determine whether an input word belong to a given linear code or is far from any codeword. In many cases, this problem corresponds to a low-degree testing problem, or a variant thereof.

In this talk, we will discuss proximity tests for multivariate polynomial codes and algebraic geometry codes, with linear-time proof generation and logarithmic verification time. Our constructions are inspired from a highly-efficient protocol which solves the Reed-Solomon proximity testing problem, called FRI protocol [Ben-Sasson, Bentov, Horesh, Riabzev. ICALP’2018]. We will first describe the FRI protocol for Reed-Solomon codes, which can be viewed as a univariate low-degree test. Then, we will show how to apply the same design principles in order to construct proximity tests with similar efficiency parameters for codes beyond Reed-Solomon codes.