論文の概要: Approximating the quantum value of an LCS game is RE-hard

• arxiv url: http://arxiv.org/abs/2507.22444v1
• Date: Wed, 30 Jul 2025 07:43:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-31 16:14:18.067953
• Title: Approximating the quantum value of an LCS game is RE-hard
• Title（参考訳）: LCSゲームの量子値の近似はre-hardである
• Authors: Aviv Taller, Thomas Vidick,
• Abstract要約: プロジェクションゲームに対するHrastadの長期コードテストの一般化を行う。 完全であり、絡み合ったプローバーに対して健全であることを示す。
• 参考スコア（独自算出の注目度）: 4.31241676251521
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We generalize H\r{a}stad's long-code test for projection games and show that it remains complete and sound against entangled provers. Combined with a result of Dong et al. \cite{Dong25}, which establishes that $\MIP^*=\RE$ with constant-length answers, we derive that $\LIN^*_{1-\epsilon,s}=\RE$, for some $1/2< s<1$ and for every sufficiently small $\epsilon>0$, where LIN refers to linearity (over $\mathbb{F}_2$) of the verifier predicate. Achieving the same result with $\epsilon=0$ would imply the existence of a non-hyperlinear group.
• Abstract（参考訳）: 我々は、H\r{a}stadの射影ゲームに対する長符号テストを一般化し、それが完備であり、絡み合ったプローバーに対して健全であることを示す。 Dong et al \cite{Dong25} の結果と組み合わさって、$\MIP^*=\RE$ が一定長の解を持つことを証明し、$\LIN^*_{1-\epsilon,s}=\RE$ が約 $1/2< s<1$ およびすべての十分小さな $\epsilon>0$ に対して与えられる。 同じ結果を$\epsilon=0$で達成することは、非超線型群の存在を意味する。

関連論文リスト

• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• 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 Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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