2026-08-21T18:02:51Z https://drops.dagstuhl.de/oai

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

Multi-Prover Interactive Proof Systems with Leakage Asadi, Vahid R. Hasegawa, Atsuya Le Gall, François Multi-prover interactive proof systems It is known that there exist multi-prover interactive protocols (MIP protocols) for the complexity class NEXP, succinct MIP protocols for NP and multi-prover interactive protocols with shared entanglement (MIP^∗ protocols) for RE. This extraordinary power of multi-prover interactive proof systems comes from the assumption that provers do not communicate with each other during the protocols. If they are allowed to communicate freely, the setting is the same as in the single-prover case, and the computational power of the system becomes significantly weaker. In this paper, we investigate for the first time the setting where communication (i.e., leakage of information) between provers is allowed but bounded. We introduce two techniques to approach this question and show that multi-prover interactive proof systems are robust against some amount of leakage. Our first technique is based on parallel repetition theorems. We apply it to show that for any polynomial p, we can construct two-prover one-round MIP and MIP^∗ protocols for NEXP and RE, respectively, that are robust against p(n) bits of leakage. We further derive our second technique to convert any low-soundness PCP construction to a two-prover one-round MIP protocol for NP robust against leakage. We also discuss the relation between robustness against leakage in multi-prover interactive proof systems and the Sliding Scale Conjecture in the PCP literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vahid R. Asadi and Atsuya Hasegawa and François Le Gall 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.60 urn:nbn:de:0030-drops-274425 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.60 eng https://creativecommons.org/licenses/by/4.0/legalcode