論文の概要: Gap-preserving reductions and RE-completeness of independent set games

• arxiv url: http://arxiv.org/abs/2505.05253v1
• Date: Thu, 08 May 2025 13:58:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-09 21:43:49.907504
• Title: Gap-preserving reductions and RE-completeness of independent set games
• Title（参考訳）: 独立集合ゲームにおけるギャップ保存還元と再完全性
• Authors: Laura Mančinska, Pieter Spaas, Taro Spirig,
• Abstract要約: 量子設定において、マルチプロデューサの対話的証明システムは非局所ゲームにおけるギャップ付き約束問題に対応する。 本稿では,量子環境におけるギャップ保存化の研究フレームワークを提案する。 MIP$*$-completeness of the gaped promise problem for the natural class of independent set games。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In complexity theory, gap-preserving reductions play a crucial role in studying hardness of approximation and in analyzing the relative complexity of multiprover interactive proof systems. In the quantum setting, multiprover interactive proof systems with entangled provers correspond to gapped promise problems for nonlocal games, and the recent result MIP$^*$=RE (Ji et al., arXiv:2001.04383) shows that these are in general undecidable. However, the relative complexity of problems within MIP$^*$ is still not well-understood, as establishing gap-preserving reductions in the quantum setting presents new challenges. In this paper, we introduce a framework to study such reductions and use it to establish MIP$^*$-completeness of the gapped promise problem for the natural class of independent set games. In such a game, the goal is to determine whether a given graph contains an independent set of a specified size. We construct families of independent set games with constant question size for which the gapped promise problem is undecidable. In contrast, the same problem is decidable in polynomial time in the classical setting. To carry out our reduction, we establish a new stability theorem, which could be of independent interest, allowing us to perturb families of almost PVMs to genuine PVMs.
• Abstract（参考訳）: 複雑性理論において、ギャップ保存還元は近似の硬さの研究や多目的対話型証明システムの相対複雑性の解析において重要な役割を果たす。 量子環境では、絡み合ったプローバーを持つ多目的対話型証明システムは非局所ゲームにおけるギャップ付き約束問題に対応し、最近のMIP$^*$=RE (Ji et al , arXiv:2001.04383) はこれらが一般に決定不能であることを示している。 しかし、MIP$^*$内の問題の相対的な複雑さは、量子環境におけるギャップ保存還元の確立が新たな課題をもたらすため、まだ十分に理解されていない。 本稿では,このような削減を研究対象とするフレームワークを導入し,独立集合ゲームの自然クラスに対するギャップ付き約束問題のMIP$^*$-完全性を確立する。 そのようなゲームにおいて、ゴールは、与えられたグラフが指定されたサイズの独立した集合を含むかどうかを決定することである。 我々は、ギャップ付き約束問題が決定不能な、一定の質問サイズを持つ独立したセットゲーム群を構築する。 対照的に、古典的な設定では多項式時間で同じ問題が決定可能である。 削減を実現するため、我々は独立した関心を持つことのできる新しい安定性定理を確立し、ほぼPVMの族を真のPVMに摂動させることを可能にした。

関連論文リスト

• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。 思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。 SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
  論文  参考訳（メタデータ） (2025-04-13T13:35:41Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [79.18735797001183]
  解法 (Stampacchia) 変分不等式 (SVIs) は最適化の中心にある基礎的な問題である。 楕円体の中心から勾配降下ステップを踏み出した後に超平面が得られる楕円体アルゴリズムの新たな変種を導入する。 主な成果のいくつかの拡張と新しい応用を提供しています。
  論文  参考訳（メタデータ） (2025-04-04T13:24:41Z)
• Fermionic Independent Set and Laplacian of an independence complex are QMA-hard [0.0]
  摂動ガジェットを用いた$k$-粒子部分空間における最適化問題はQMAハードであることが証明された。 自然位相データ解析問題 QMA-hard の最初の例を示す。
  論文  参考訳（メタデータ） (2024-11-05T16:21:48Z)
• Sample Complexity of Locally Differentially Private Quantum Hypothesis Testing [10.14555083237668]
  異なる設定に対して、達成可能性と逆バウンダリを提供します。 これには、様々なレジームにおける対称状態の識別と非対称ケースが含まれる。 この取り組みにおける重要なツールは、私たちが独立した関心を持つと信じている新しいエントロピーの不平等である。
  論文  参考訳（メタデータ） (2024-06-26T18:00:19Z)
• Scalable unsupervised alignment of general metric and non-metric structures [21.29255788365408]
  異なるドメインからのデータのアライメントは、非常に異なる領域にわたる幅広いアプリケーションによる機械学習の基本的な問題である。 我々は、2次代入問題 (QAP) の最小化問題でもある、関連よく計算可能な線形代入問題 (LAP) を学習する。 単一セルマルチオミクスとニューラル潜在空間からの合成および実データに対するアプローチを評価する。
  論文  参考訳（メタデータ） (2024-06-19T12:54:03Z)
• Learning the Expected Core of Strictly Convex Stochastic Cooperative Games [17.85094087244095]
  報酬配分における重要な概念は、大連立から逸脱する動機を持つエージェントがいない安定した配分の集合である。 我々は,多くのサンプルが与えられた期待コアの点を返すtextttCommonPoints-Picking というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-10T23:49:49Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  我々は、軽度の仮定の下で、識別性と学習可能性に関する保証を提供する。 我々は,線形制約付き結合テンソル分解に基づく効率的なアルゴリズムを開発し,スケーラブルで保証可能な解を得る。
  論文  参考訳（メタデータ） (2021-01-17T07:48:45Z)

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

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