論文の概要: 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 16:54:31.365121
• Title: The Aldous--Lyons Conjecture II: Undecidability
• Title（参考訳）: Aldous-Lyons Conjecture II: Undecidability
• Abstract要約: 調整された非局所ゲームである$G$が与えられた場合、$G$が特別な種類の完全戦略を持つ場合と、$G$のすべての戦略が完璧ではない場合とを区別することは決定不可能である。 共役紙 [BCLV24] に導入された還元を用いて、この不決定性の結果はアルドゥス=リヨン予想に対する負の答えを意味する。
• 参考スコア（独自算出の注目度）: 3.8370118222043694
• License: http://creativecommons.org/licenses/by/4.0/
• 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 Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Auditing an AI-Generated Mathematical Proof: A Correction to a Greedy Conditioning Lemma in Quantum Parallel Repetition [0.0]
  このメモは明示的な反例を与え、意図された継続条件を特定し、完全な正当性証明を提供する。 しかし、これは主並列反復定理の独立な検証として解釈されるべきではない。
  論文  参考訳（メタデータ） (2026-08-03T15:12:46Z)
• Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials [2.5782420501870296]
  一定の$s$に対して、$s$サーバのプライベート情報検索プロトコルが存在することを示す。 我々の数論予想は既存の予想によって示唆される。
  論文  参考訳（メタデータ） (2026-07-24T06:59:30Z)
• Odds Law: The Decomposition Algebra On How Intelligence Organizes Itself to Solve Difficult Problems Reliably [0.5414847001704247]
  信頼性は、合成によって配置された独立した情報で購入され、検証者によって拘束されることを示す。 つまり、信頼性は自由でも魔法でもなく、独立した情報で購入され、構成によって配置され、検証者によって拘束される。
  論文  参考訳（メタデータ） (2026-06-14T09:53:11Z)
• Yanasse: Finding New Proofs from Deep Vision's Analogies, Part 1 [51.56484100374058]
  システムはマドリブの27の上位領域の戦術的利用分布を抽出する。 zスコアを計算して、ソースエリアで多用されるが、ターゲットエリアで稀または欠落している戦術を特定する。 これは、GPUアクセラレーションされたNPハードアナログを用いて、ソースとターゲットの証明状態と一致する。
  論文  参考訳（メタデータ） (2026-04-19T03:27:16Z)
• Choices and their Provenance: Explaining Stable Solutions of Abstract Argumentation Frameworks [1.4064491732635236]
  本稿では、この証明を安定なAFソリューションに拡張するための新しいアプローチを提案する。 我々のアプローチでは、最小限のクリティカルアタックのセットを特定し、安定モデルによる選択と仮定をピンポイントする。
  論文  参考訳（メタデータ） (2025-06-01T17:09:55Z)
• Cloning Games, Black Holes and Cryptography [53.93687166730726]
  クローンゲーム解析のための新しいツールキットを提案する。 これらのゲームは、より定量的なノンクローズング(no-cloning)バージョンをキャプチャし、ブロック不能暗号の中心となる。
  論文  参考訳（メタデータ） (2024-11-07T14:09:32Z)
• 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)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• 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)
• MIP*=RE [9.42581332803306]
  言語のクラス MIP* は、複数の量子プロバーサを共有する絡み合いと相互作用する古典的検証器によって決定できることを示す。 我々は、フォン・ノイマン代数のコンヌの理論の難解性を提供する。
  論文  参考訳（メタデータ） (2020-01-13T16:32:40Z)

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

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