論文の概要: Efficiently Batching Unambiguous Interactive Proofs

• arxiv url: http://arxiv.org/abs/2510.19075v1
• Date: Tue, 21 Oct 2025 21:04:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:14.720783
• Title: Efficiently Batching Unambiguous Interactive Proofs
• Title（参考訳）: 曖昧な対話的証明を効果的にバッチする
• Authors: Bonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman Kalai,
• Abstract要約: 例えば、$Lotimes k$に属するステートメントのセット$k$-tuplesは、複雑さを伴うあいまいなインタラクティブな証明を持つ。 $ellcdotmathsfpolylog(k)$、$acdot ellcdotmathsfpolylog(k)$、ラウンドごとの通信である。
• 参考スコア（独自算出の注目度）: 8.993111413196559
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that if a language $L$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where $a$ bits are communicated per round, then the batch language $L^{\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $L$, has an unambiguous interactive proof with round complexity $\ell\cdot\mathsf{polylog}(k)$, per-round communication of $a\cdot \ell\cdot\mathsf{polylog}(k) + \mathsf{poly}(\ell)$ bits, assuming the verifier in the $\mathsf{UIP}$ has depth bounded by $\mathsf{polylog}(k)$. Prior to this work, the best known batch $\mathsf{UIP}$ for $L^{\otimes{k}}$ required communication complexity at least $(\mathsf{poly}(a)\cdot k^{\epsilon} + k) \cdot \ell^{1/\epsilon}$ for any arbitrarily small constant $\epsilon>0$ (Reingold-Rothblum-Rothblum, STOC 2016). As a corollary of our result, we obtain a doubly efficient proof system, that is, a proof system whose proving overhead is polynomial in the time of the underlying computation, for any language computable in polynomial space and in time at most $n^{O\left(\sqrt{\frac{\log n}{\log\log n}}\right)}$. This expands the state of the art of doubly efficient proof systems: prior to our work, such systems were known for languages computable in polynomial space and in time $n^{({\log n})^\delta}$ for a small $\delta>0$ significantly smaller than $1/2$ (Reingold-Rothblum-Rothblum, STOC 2016).
• Abstract（参考訳）: 例えば、$L$に属する文の集合の$k$-tuplesは、ラウンド複雑性を持つ不明確なインタラクティブな証明を持ち、$a\cdot \ell\cdot\mathsf{polylog}(k)$, per-round communication of $a\cdot \ell\cdot\mathsf{polylog}(k) + \mathsf{polylog}(k) + \mathsf{polylog}(\ell)$ bits, assuming the verifier in the $\mathsf{UIP} has bounded $mathsf{polylog}(k)$である。 この研究に先立ち、最もよく知られているバッチ $\mathsf{UIP}$ for $L^{\otimes{k}}$ 必要な通信複雑性は少なくとも$(\mathsf{poly}(a)\cdot k^{\epsilon} + k) \cdot \ell^{1/\epsilon}$ 任意の小さな定数 $\epsilon>0$ (Reingold-Rothblum-Rothblum, STOC 2016)である。 結果のまとめとして、多項式空間で計算可能な任意の言語に対して、基礎となる計算の時点で多項式であることが証明された証明系を、最大で$n^{O\left(\sqrt{\frac {\log n}{\log n}}\right)}$とする。 我々の研究の前には、これらのシステムは多項式空間で計算可能な言語で知られており、小さな$\delta>0$に対して$n^{({\log n})^\delta}$は1/2$(Reingold-Rothblum-Rothblum, STOC 2016)よりもかなり小さかった。

関連論文リスト

• $\mathsf{P} \neq \mathsf{NP}$: A Non-Relativizing Proof via Quantale Weakness and Geometric Complexity [0.0]
  We work in the weak Quantale $w_Q=K_mathrmpoly(cdotmidcdot)$. ランダムな3ドルCNFをマスキングした効率よくサンプリング可能なアンサンブル$D_m$に対して、スイッチング・バイ・ウェイクネスの正規形式を証明する。
  論文  参考訳（メタデータ） (2025-10-09T21:01:17Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• 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)
• 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)

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

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