Computer Science/Discrete Mathematics Seminar II

A common tool in the construction of probabilistically checkable proofs is low degree encodings. Babai, Fortnow and Lund proved the local testability of the individual low degree code, and used it to provide a multi-prover interactive proof (MIP) protocol for every non-deterministic exponential time (NEXP) language. In 2019, Ji, Natarajan, Vidick, Wright and Yuen settled the analogous quantum question, showing that there is a quantum MIP protocol (MIP*) for every recursively enumerable (RE) language. Arguably, the most technical part in their argument is the quantum local testability of the individual low degree code. I aim to present both the classical and quantum local testability results with some detail