2026-08-21T17:56:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27383 2026-08-21T14:42:37Z ddc:004 open_access

Highly-Efficient Local Proofs and Codes (Invited Talk) Ron-Zewi, Noga Interactive oracle proofs probabilistically-checkable proofs error-correcting codes Interactive oracle proofs (IOPs) extend the classical notion of probabilistically-checkable proofs (PCPs) by allowing a verifier to interact with a prover over a small number of rounds, while querying the prover’s messages in only a few locations. A recent line of work gave highly-efficient IOPs outperforming state-of-the-art PCPs, for example, constant-round and constant-query (ZK-)IOPs with only a linear (and even approaching the witness length) amount of communication, as well as (ZK-)IOPs with linear-time prover complexity. These constructions were leveraged in turn to obtain highly-efficient succinct arguments and zero-knowledge proofs. The improved efficiency was obtained by replacing polynomial-based codes, commonly used in such proof systems, with more efficient (tensor-based) codes. In particular, these constructions bypassed a barrier imposed by the need to encode the computation using a multiplication code. In the talk I will survey these highly-efficient IOP constructions, and highlight some interesting open problems raised by these works. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noga Ron-Zewi 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.2 urn:nbn:de:0030-drops-273836 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.2 eng https://creativecommons.org/licenses/by/4.0/legalcode