Multi-Prover Interactive Proof Systems with Leakage

• URL: http://arxiv.org/abs/2605.09872v2
• Date: Sat, 16 May 2026 06:56:53 GMT
• Title: Multi-Prover Interactive Proof Systems with Leakage
• Abstract summary: We introduce two techniques to approach the setting where communication between provers is allowed but bounded.<n>We show that for any $p$, we can construct two-prover one-round $mathsfMIP$ and $mathsfMIPast$ protocols for $mathsfNEXP$ and $mathsfRE$.
• Score: 1.0960289997471082
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is known that there exist multi-prover interactive protocols ($\mathsf{MIP}$ protocols) for the complexity class $\mathsf{NEXP}$, succinct $\mathsf{MIP}$ protocols for $\mathsf{NP}$ and multi-prover interactive protocols with shared entanglement ($\mathsf{MIP}^\ast$ protocols) for $\mathsf{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 $\mathsf{MIP}$ and $\mathsf{MIP}^\ast$ protocols for $\mathsf{NEXP}$ and $\mathsf{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 $\mathsf{MIP}$ protocol for $\mathsf{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.

Related papers

• Magic and communication complexity [0.6533091401094101]
  We establish novel connections between magic in quantum circuits and communication complexity.<n>We show that functions computable with low magic have low communication cost.
  arXiv  Detail & Related papers  (2025-10-08T17:14:25Z)
• QIP $ \subseteq $ AM(2QCFA) [0.0]
  We show that $mathsfPSPACE$ is subset of $mathsfAM (2QCFA)$, the class of languages having Arthur-Merlin proof systems.<n>Our protocols use only rational-valued quantum transitions and run in double-exponential expected time.
  arXiv  Detail & Related papers  (2025-08-28T17:22:31Z)
• ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving [53.67926215943612]
  $rm Psmall ROOFWsmall ALA$ allows interaction between neural theorem-provers and two established interactive proof assistants (ITPs)<n>We show that a model trained on a mix of $rm Psmall ROOFWsmall ALA$-generated Coq and Lean data outperforms Lean-only and Coq-only models on the standard prove-at-$k$ metric.
  arXiv  Detail & Related papers  (2025-02-07T05:35:46Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• On the Power of Interactive Proofs for Learning [3.785008536475385]
  We continue the study of doubly-efficient proof systems for verifying PAC learning. We construct an interactive protocol for learning the largest Fourier characters of a given function $f colon 0,1n to 0,1$ up to an arbitrarily small error. We show that if we do not insist on doubly-efficient proof systems, then the model becomes trivial.
  arXiv  Detail & Related papers  (2024-04-11T23:16:21Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• A direct product theorem for quantum communication complexity with applications to device-independent cryptography [6.891238879512672]
  We show that for a distribution $p$ that is product across the input sets of the $l$ players, the success probability of any entanglement-assisted quantum communication protocol goes down exponentially in $n$. We also show that it is possible to do device-independent (DI) quantum cryptography without the assumption that devices do not leak any information.
  arXiv  Detail & Related papers  (2021-06-08T12:52:10Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  We show that the class $mathsfMIP*$ is equal to $mathsfRE$. In particular this shows that the complexity of approximating the quantum value of a non-local game $G$ is equivalent to the complexity of the Halting problem.
  arXiv  Detail & Related papers  (2020-02-24T19:11:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.