論文の概要: Multi-Prover Interactive Proof Systems with Leakage
- arxiv url: http://arxiv.org/abs/2605.09872v2
- Date: Sat, 16 May 2026 06:56:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-19 23:51:08.24416
- Title: Multi-Prover Interactive Proof Systems with Leakage
- Title（参考訳）: 漏洩を考慮した多目的対話型証明システム
- Authors: Vahid R. Asadi, Atsuya Hasegawa, François Le Gall,
- Abstract要約: 本稿では,プロデューサ間の通信が許されるが境界づけられた設定にアプローチする2つの手法を提案する。
任意の$p$に対して、$mathsfNEXP$と$mathsfRE$に対して$mathsfMIPast$と$mathsfMIPast$プロトコルを構築することができる。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 複雑性クラス $\mathsf{NEXP}$, succinct $\mathsf{MIP}$ Protocol for $\mathsf{NP}$ と共有エンタングルメント$\mathsf{MIP}^\ast$ protocol for $\mathsf{RE}$ のマルチプロプライエタリなプロトコル($\mathsf{MIP}$ protocol)が存在することが知られている。
マルチプロの対話型証明システムのこの並外れた力は、プロトコルの間、プローバーが互いに通信しないという仮定に由来する。
自由な通信が許される場合、設定はシングルプロの場合と同じであり、システムの計算能力は著しく弱くなる。
本稿では,プローバ間の通信(すなわち情報漏洩)が許されるが拘束される設定を初めて検討する。
本稿では,この問題に対処する2つの手法を導入し,複数プロデューサの対話型証明システムがある程度の漏洩に対して堅牢であることを示す。
最初の手法は並列反復定理に基づいている。
任意の多項式$p$に対して、それぞれ$p(n)$ビットのリークに対して堅牢な、$\mathsf{MIP}$と$\mathsf{MIP}^\ast$ Protocol for $\mathsf{NEXP}$と$\mathsf{RE}$を構成できることを示す。
さらに、低音域PCPの構成を、リークに対するロバストな$\mathsf{MIP}$プロトコルの2つのプロプライエタリな1ラウンドの$\mathsf{NP}$プロトコルに変換するための2番目の手法を導出する。
また,多目的対話型証明システムにおける漏洩に対するロバスト性とPCP文献におけるスライディングスケール・コンジェクチャの関係についても考察する。
関連論文リスト
- Magic and communication complexity [0.6533091401094101]
量子回路におけるマジックと通信複雑性の間の新しい接続を確立する。
低魔法で計算可能な関数は通信コストが低いことを示す。
論文 参考訳（メタデータ） (2025-10-08T17:14:25Z) - QIP $ \subseteq $ AM(2QCFA) [0.0]
我々は、$mathsfPSPACE$は、Arthur-Merlin証明システムを持つ言語のクラスである$mathsfAM (2QCFA)$のサブセットであることを示す。
我々のプロトコルは、有理値量子遷移のみを使用し、二重指数期待時間で実行される。
論文 参考訳（メタデータ） (2025-08-28T17:22:31Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - On the Power of Interactive Proofs for Learning [3.785008536475385]
我々は、PAC学習を検証するための2倍効率の証明システムの研究を継続する。
任意の関数$f colon 0,1n から 0,1$ までの最大フーリエ文字を任意に小さな誤りまで学習するための対話的プロトコルを構築する。
二重効率証明系を主張しないならば、モデルは自明になる。
論文 参考訳（メタデータ） (2024-04-11T23:16:21Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - A direct product theorem for quantum communication complexity with
applications to device-independent cryptography [6.891238879512672]
我々は、$l$プレーヤの入力集合にまたがる分布である$p$に対して、任意の絡み合い支援量子通信プロトコルの成功確率は、$n$で指数関数的に低下することを示した。
また、デバイスが情報を漏らさないという仮定なしに、デバイス非依存(DI)量子暗号が可能であることも示している。
論文 参考訳（メタデータ） (2021-06-08T12:52:10Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - On the complexity of zero gap MIP* [0.11470070927586014]
クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
論文 参考訳（メタデータ） (2020-02-24T19:11:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。