論文の概要: Compiling Any $\mathsf{MIP}^{*}$ into a (Succinct) Classical Interactive Argument

• arxiv url: http://arxiv.org/abs/2510.08495v1
• Date: Thu, 09 Oct 2025 17:35:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:15.251489
• Title: Compiling Any $\mathsf{MIP}^{*}$ into a (Succinct) Classical Interactive Argument
• Title（参考訳）: Any$\mathsf{MIP}^{*}$を(簡潔な)古典的インタラクティブな引数にコンパイルする
• Authors: Andrew Huang, Yael Tauman Kalai,
• Abstract要約: 我々は、$mathsfMIP*$プロトコルを簡潔な対話的引数に変換するジェネリックコンパイラを提案する。 a such compiler for $mathsfMIP*$ was given by Kalai, Lombardi, Vaikuntanathan and Yang (STOC 2022)
• 参考スコア（独自算出の注目度）: 3.49781504808707
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a generic compiler that converts any $\mathsf{MIP}^{*}$ protocol into a succinct interactive argument where the communication and the verifier are classical, and where post-quantum soundness relies on the post-quantum sub-exponential hardness of the Learning with Errors ($\mathsf{LWE}$) problem. Prior to this work, such a compiler for $\mathsf{MIP}^{*}$ was given by Kalai, Lombardi, Vaikuntanathan and Yang (STOC 2022), but the post-quantum soundness of this compiler is still under investigation. More generally, our compiler can be applied to any $\mathsf{QIP}$ protocol which is sound only against semi-malicious provers that follow the prescribed protocol, but with possibly malicious initial state. Our compiler consists of two steps. We first show that if a language $\mathcal{L}$ has a $\mathsf{QIP}$ with semi-malicious soundness, where the prover runs in time $T$, then $\mathcal{L} \in \mathsf{QMATIME}(T)$. Then we construct a succinct classical argument for any such language, where the communication complexity grows polylogarithmically with $T$, under the post-quantum sub-exponential hardness of $\mathsf{LWE}$.
• Abstract（参考訳）: 本稿では,任意の$\mathsf{MIP}^{*}$プロトコルを,通信と検証器が古典的であるような簡潔な対話的引数に変換する汎用コンパイラを提案する。 この研究の前に、$\mathsf{MIP}^{*}$ のコンパイラは Kalai, Lombardi, Vaikuntanathan and Yang (STOC 2022) によって与えられたが、このコンパイラのクォータム後の健全性はまだ調査中である。 より一般的に、我々のコンパイラは任意の$\mathsf{QIP}$プロトコルに適用できます。 私たちのコンパイラは2つのステップで構成されています。 最初に、ある言語 $\mathcal{L}$ が半重複音を持つ $\mathsf{QIP}$ を持つ場合、証明者は時間$T$, $\mathcal{L} \in \mathsf{QMATIME}(T)$ で実行される。 すると、そのような言語に対する簡潔な古典的引数を構築し、通信複雑性は、$T$と多元的に増加し、$\mathsf{LWE}$のポストクォータム部分指数硬度の下で、$T$となる。

関連論文リスト

• 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)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• On relating one-way classical and quantum communication complexities [6.316693022958221]
  通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。 量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
  論文  参考訳（メタデータ） (2021-07-24T14:35:09Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。 特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
  論文  参考訳（メタデータ） (2020-02-24T19:11:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。