論文の概要: The complexity of entangled graph colouring via polymorphisms

• arxiv url: http://arxiv.org/abs/2610.02565v1
• Date: Thu, 01 Oct 2026 22:58:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.117604
• Title: The complexity of entangled graph colouring via polymorphisms
• Title（参考訳）: 多型による絡み合ったグラフ色付けの複雑さ
• Abstract要約: CSP間のポリモルフィズムに基づく還元は、多型間の絡み合った類似性に基づいて、絡み合ったCSP間のギャップ保存的還元に一般化できることを示す。 この減少により,3色以上の絡み合ったグラフの色付けの不決定性を示すことができ,これは可換性ガジェットによる事前の硬さ低減に抵抗性があることが証明された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of classes of nonlocal games. Due to the CSP dichotomy theorem, the complexity of constraint satisfaction problems with classical assignments can be fully understood by studying the symmetries of the CSP, in terms of the polymorphisms of the underlying relational structure. In this work, we show that the polymorphism-based reductions between CSPs can be generalised to gap-preserving reductions between entangled CSPs based on an entangled analogue of the polymorphisms. This reduction allows us to show undecidability of entangled graph colouring with more than three colours, a problem that has proved resistant to prior hardness reductions based on commutativity gadgets.
• Abstract（参考訳）: 変数に対する演算子代入を伴う制約満足度問題(CSP)は、非局所ゲームのクラスの絡み合った値の決定複雑性を研究するために、よく構造化された設定を提供する。 CSPの二分法定理により、古典的な代入を伴う制約満足度問題の複雑性は、基礎となる関係構造の多型の観点から、CSPの対称性を研究することによって完全に理解することができる。 本研究では、多型間の多型に基づく還元が、多型間の共形類似に基づく共形CSP間のギャップ保存還元に一般化可能であることを示す。 この減少により,3色以上の絡み合ったグラフの色付けの不決定性を示すことができ,これは可換性ガジェットによる事前の硬さ低減に抵抗性があることが証明された。

関連論文リスト

• PathAR: Structure-First Autoregressive Synthesis of Multimodal Pathology Images [51.428093790826814]
  そこで我々は, モーダリティ・ラベル条件付き病理モデル (PathAR) を用いて, 構造と外観を分解し, 自己回帰モデル(PathAR)を提案する。 PathARは、不均一なモダリティ固有の外観下で形態を安定化し、空間的に整列したイメージマスクペア生成を可能にする。
  論文  参考訳（メタデータ） (2026-06-01T01:43:48Z)
• On the Generalization Bounds of Symbolic Regression with Genetic Programming [7.208302351825167]
  遺伝的プログラミングモデルを用いたシンボリック回帰の学習理論解析を行う。 我々は、木の大きさ、深さ、学習可能な定数の制約の下で、GPスタイルのSRに対して有界な一般化を導出する。 我々の研究は、GPベースのSRにおいて一般的に観察される経験的行動について、原則化された説明を提供する。
  論文  参考訳（メタデータ） (2026-04-19T12:12:11Z)
• LLM Probing with Contrastive Eigenproblems: Improving Understanding and Applicability of CCS [0.17188280334580197]
  最適化されるべきなのは、相対的なコントラスト一貫性である、と私たちは主張する。 我々は CCS を固有確率として再構成し、解釈可能な固有値と複数の変数への自然な拡張を持つ閉形式解を得る。 この結果から,コントラスト整合性の相対性化はCSの理解を向上するだけでなく,より広範な探索や機械的解釈可能性手法の道を開くことが示唆された。
  論文  参考訳（メタデータ） (2025-11-03T22:00:37Z)
• Quantum Advantage and CSP Complexity [1.90365714903665]
  関係構造間の準同型によってモデル化された情報処理タスクは、エンタングルメントを計算資源として使用する場合、量子的優位性を見極めることができる。 量子優位性の発生は、CSPの多型IDをキャプチャする同じタイプの代数構造によって決定されることを示す。
  論文  参考訳（メタデータ） (2024-04-19T21:23:03Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。 我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。 全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Controlling the Complexity and Lipschitz Constant improves polynomial nets [55.121200972539114]
  多項式ネットの結合CP分解(CCP)モデルとNested Coupled CP分解(NCP)モデルに対する新しい複雑性境界を導出する。 本研究では、6つのデータセットで実験的に評価し、モデルが逆摂動に対して頑健であるとともに精度も向上することを示す。
  論文  参考訳（メタデータ） (2022-02-10T14:54:29Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Semantic Correspondence with Transformers [68.37049687360705]
  本稿では,変換器を用いたコストアグリゲーション(CAT)を提案し,意味論的に類似した画像間の密接な対応を見出す。 初期相関マップと多レベルアグリゲーションを曖昧にするための外観親和性モデリングを含む。 提案手法の有効性を示す実験を行い,広範囲にわたるアブレーション研究を行った。
  論文  参考訳（メタデータ） (2021-06-04T14:39:03Z)
• Rethinking conditional GAN training: An approach using geometrically structured latent manifolds [58.07468272236356]
  条件付きGAN(cGAN)は、生成された出力の多様性の欠如などの重大な欠点に悩まされる。 本稿では,バニラcGANの多様性と視覚的品質を両立させる新しいトレーニング機構を提案する。
  論文  参考訳（メタデータ） (2020-11-25T22:54:11Z)
• On SCC-recursiveness in Quantitative Argumentation [0.0]
  SCC再帰性はファジィ拡張セマンティクスに適していることを示す。 SCC再帰性はファジィ拡張セマンティクスを特徴付ける代替手法であることを示す。
  論文  参考訳（メタデータ） (2020-06-16T02:33:06Z)
• Stochastic spectral embedding [0.0]
  確率スペクトル埋め込み(SSE)に基づく新しい逐次適応サロゲートモデリング法を提案する。 本手法は,複雑性と入力次元の異なるモデルの集合上で,最先端のスパースカオス展開に対して,どのように好意的に比較されるかを示す。
  論文  参考訳（メタデータ） (2020-04-09T11:00:07Z)

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

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