論文の概要: The Aldous--Lyons Conjecture II: Undecidability

• arxiv url: http://arxiv.org/abs/2501.00173v1
• Date: Mon, 30 Dec 2024 22:59:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-05 20:43:23.196322
• Title: The Aldous--Lyons Conjecture II: Undecidability
• Title（参考訳）: Aldous-Lyons Conjecture II: Undecidability
• Authors: Lewis Bowen, Michael Chapman, Thomas Vidick,
• Abstract要約: 調整された非局所ゲームである$G$が与えられた場合、$G$が特別な種類の完全戦略を持つ場合と、$G$のすべての戦略が完璧ではない場合とを区別することは決定不可能である。 共役紙 [BCLV24] に導入された還元を用いて、この不決定性の結果はアルドゥス=リヨン予想に対する負の答えを意味する。
• 参考スコア（独自算出の注目度）: 3.8370118222043694
• License:
• Abstract: This paper, and its companion [BCLV24], are devoted to a negative resolution of the Aldous--Lyons Conjecture [AL07, Ald07]. In this part we study tailored non-local games. This is a subclass of non-local games -- combinatorial objects which model certain experiments in quantum mechanics, as well as interactive proofs in complexity theory. Our main result is that, given a tailored non-local game $G$, it is undecidable to distinguish between the case where $G$ has a special kind of perfect strategy, and the case where every strategy for $G$ is far from being perfect. Using a reduction introduced in the companion paper [BCLV24], this undecidability result implies a negative answer to the Aldous--Lyons conjecture. Namely, it implies the existence of unimodular networks that are non-sofic. To prove our result, we use a variant of the compression technique developed in MIP*=RE [JNV+21]. Our main technical contribution is to adapt this technique to the class of tailored non-local games. The main difficulty is in establishing answer reduction, which requires a very careful adaptation of existing techniques in the construction of probabilistically checkable proofs. As a byproduct, we are reproving the negation of Connes' embedding problem [Con76] -- i.e., the existence of a $\mathrm{II}_1$-factor which cannot be embedded in an ultrapower of the hyperfinite $\mathrm{II}_1$-factor -- first proved in [JNV+21], using an arguably more streamlined proof. In particular, we incorporate recent simplifications from the literature [dlS22b, Vid22] due to de la Salle and the third author.
• Abstract（参考訳）: 本論文とその共用体 [BCLV24] は、Aldous-Lyons Conjecture [AL07, Ald07] の負の分解能に特化している。 本項では,非局所ゲームについて考察する。 これは非局所ゲーム(英語版)のサブクラスであり、量子力学における特定の実験をモデル化する組合せ対象と、複雑性理論におけるインタラクティブな証明である。 我々の主な結果は、調整された非ローカルゲームである$G$を考えると、$G$が特別な種類の完璧な戦略を持つ場合と、$G$のすべての戦略が完璧ではない場合とを区別することは不可能である。 共役紙 [BCLV24] に導入された還元を用いて、この不決定性の結果はアルドゥス=リヨン予想に対する負の答えを意味する。 すなわち、非正則な一モジュラーネットワークの存在を意味する。 MIP*=RE [JNV+21]で開発された圧縮手法の変種を用いる。 我々の主な技術的貢献は、このテクニックを調整された非ローカルゲームに適応させることです。 主な課題は、確率論的に検証可能な証明を構築する際に、既存の手法を非常に慎重に適用する必要がある解の削減を確立することである。 副産物として、コーンズの埋め込み問題 [Con76] -- すなわち、超有限$\mathrm{II}_1$-factor -- [JNV+21] で最初に証明された超有限$\mathrm{II}_1$-factor -- に埋め込むことができない$\mathrm{II}_1$-factorの存在を、より簡潔な証明を用いて証明する。 特に、ド・ラ・サルと第3の著者による文献(dlS22b, Vid22)の最近の単純化を取り入れた。

関連論文リスト

• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。 本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。 我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
  論文  参考訳（メタデータ） (2024-08-27T18:28:31Z)
• Efficiently stable presentations from error-correcting codes [5.69361786082969]
  線形誤り訂正符号から$mathbbZk$のプレゼンテーションを構築するための一般的な方法を提案する。 結果のプレゼンテーションは、コードがエフェクト可能なときの安定性が弱いことを観察する。 このことは一般には証明できないが、量子情報理論における非局所ゲームの研究において最近の結果を活用する。
  論文  参考訳（メタデータ） (2023-11-08T13:40:13Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。 また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
  論文  参考訳（メタデータ） (2022-09-16T13:59:42Z)
• Agnostic Online Learning and Excellent Sets [21.87574015264402]
  我々は、$k$-edge 安定グラフにおける大きな可分集合の存在を証明した。 これらの証明のテーマは、測度から生じる2つの抽象的な多数派概念と、階数や次元から生じる相互作用である。
  論文  参考訳（メタデータ） (2021-08-12T07:33:33Z)
• A monogamy-of-entanglement game for subspace coset states [7.716156977428555]
  この性質は、最近 [Coladangelo, Liu, Liu, and Zhandry, Crypto'21] によって予想され、擬似ランダム関数の復号化と複写保護に応用できることを示した。 BB'84状態に基づく単純なモノガミーゲームに解析を還元するために,本論文の手法を直接追従する2つの証明と,[Vidick and Zhang, Euro'20] からの観察を用いた証明を提案する。
  論文  参考訳（メタデータ） (2021-07-28T12:41:39Z)
• Counterexamples to the Low-Degree Conjecture [80.3668228845075]
  ホプキンスの予想は、ある高次元仮説テスト問題に対して、非時間アルゴリズムはいわゆる「単純な統計」よりも優れていると仮定する。 この予想は、統計対計算のトレードオフを理解しようとする最近の研究のラインを囲む信念を定式化する。
  論文  参考訳（メタデータ） (2020-04-17T21:08:11Z)
• MIP*=RE [9.42581332803306]
  言語のクラス MIP* は、複数の量子プロバーサを共有する絡み合いと相互作用する古典的検証器によって決定できることを示す。 我々は、フォン・ノイマン代数のコンヌの理論の難解性を提供する。
  論文  参考訳（メタデータ） (2020-01-13T16:32:40Z)

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

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