論文の概要: Arkhipov's theorem, graph minors, and linear system nonlocal games

• arxiv url: http://arxiv.org/abs/2205.04645v2
• Date: Mon, 18 Jul 2022 18:40:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-13 18:00:02.618111
• Title: Arkhipov's theorem, graph minors, and linear system nonlocal games
• Title（参考訳）: arkhipovの定理、グラフマイナー、線形系非局所ゲーム
• Authors: Connor Paddock, Vincent Russo, Turner Silverthorne, and William Slofstra
• Abstract要約: 本稿では,2色グラフの入射系を基礎とするグラフ入射ゲームの解群について検討する。 アルキポフの定理は、連結グラフのグラフ入射ゲームが完全量子戦略を持つことは、それが完全古典的戦略を持つか、あるいはグラフが非平面的であることを言う。 我々はアルキポフの定理を拡張し、連結な2色グラフのグラフ入射ゲームに対して、解群のすべての商閉性は禁じられたマイナーな性質を持つことを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The perfect quantum strategies of a linear system game correspond to certain representations of its solution group. We study the solution groups of graph incidence games, which are linear system games in which the underlying linear system is the incidence system of a (non-properly) two-coloured graph. While it is undecidable to determine whether a general linear system game has a perfect quantum strategy, for graph incidence games this problem is solved by Arkhipov's theorem, which states that the graph incidence game of a connected graph has a perfect quantum strategy if and only if it either has a perfect classical strategy, or the graph is nonplanar. Arkhipov's criterion can be rephrased as a forbidden minor condition on connected two-coloured graphs. We extend Arkhipov's theorem by showing that, for graph incidence games of connected two-coloured graphs, every quotient closed property of the solution group has a forbidden minor characterization. We rederive Arkhipov's theorem from the group theoretic point of view, and then find the forbidden minors for two new properties: finiteness and abelianness. Our methods are entirely combinatorial, and finding the forbidden minors for other quotient closed properties seems to be an interesting combinatorial problem.
• Abstract（参考訳）: 線形システムゲームの完全量子戦略は、その解群の特定の表現に対応する。 本研究では,(プロプライエタリでない)2色グラフの入射系を基本とする線形系ゲームであるグラフ入射ゲームの解群について検討する。 一般線形系ゲームが完全な量子戦略を持っているかどうかは決定できないが、グラフ入射ゲームの場合、この問題はarkhipovの定理によって解決され、連結グラフのグラフ入射ゲームが完全な量子戦略を持つのは、それが完全古典戦略を持つか、あるいはグラフが平面的でないかのときのみである。 アルキポフの基準は、連結な2色グラフ上の禁止されたマイナー条件として記述することができる。 我々はアルキポフの定理を拡張し、連結二色グラフのグラフ入射ゲームに対して、解群のすべての商閉性は禁じられたマイナーな性質を持つことを示した。 アーキポフの定理を群論的な観点から再定義し、有限性とアーベル性という2つの新しい性質に対する禁止マイナーを見つける。 我々の手法は完全に組合せ的であり、他の商閉性質に対する禁止マイナーを見つけることは興味深い組合せ問題である。

関連論文リスト

• A Systematization of the Wagner Framework: Graph Theory Conjectures and Reinforcement Learning [0.3111424566471946]
  アダム・ゾルト・ワグナー(Adam Zsolt Wagner)はReinforcement Learning (RL) を用いたグラフ理論の予想を解き放つアプローチを提案した。 様々なRLアルゴリズムを用いた4つの異なるシングルプレイヤーグラフ構築ゲームを提案する。 また、任意の予想に対して最も適切なニューラルネットワークアーキテクチャを選択するための原則的アプローチを提案する。
  論文  参考訳（メタデータ） (2024-06-18T14:40:20Z)
• Communication Complexity of Graph Isomorphism, Coloring, and Distance Games [0.0]
  最適な条件下では,完全非署名戦略が通信複雑性を崩壊させることを示す。 意外なことに、非シグナリング戦略は、古典的および量子的戦略と比較して、新しいゲームにとってより微妙な区別を提供する。
  論文  参考訳（メタデータ） (2024-06-04T10:53:16Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。 幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。 次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
  論文  参考訳（メタデータ） (2023-05-05T14:04:52Z)
• Learning Universe Model for Partial Matching Networks over Multiple Graphs [78.85255014094223]
  2つまたは複数のグラフの部分的マッチングのための宇宙マッチングスキームを開発する。 不整合及び不整合検出のための微妙なロジックを、明確にモデル化することができる。 これは、2グラフマッチング、複数グラフマッチング、オンラインマッチング、混合グラフマッチングを同時に扱うことができる最初のディープラーニングネットワークである。
  論文  参考訳（メタデータ） (2022-10-19T08:34:00Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  一般作用素空間から C$*$-代数の双対への線型写像が与えられたとき、その完全有界ノルムは、その$(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  論文  参考訳（メタデータ） (2021-12-09T21:06:52Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• The quantum-to-classical graph homomorphism game [0.0]
  量子グラフと古典グラフの間のグラフ準同型ゲームを導入する。 ゲームに対する様々な量子モデルの勝利戦略は、非可換グラフ準同型の概念の類似であることを示す。 また、全ての量子完備グラフの明示的な量子色付けを実証し、量子グラフに対する4ドルの色付けゲームの代数は常に非自明なものであるという驚くべき事実を導いた。
  論文  参考訳（メタデータ） (2020-09-15T17:09:35Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。 位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
  論文  参考訳（メタデータ） (2020-08-11T17:58:13Z)
• Synchronous linear constraint system games [0.0]
  ゲーム代数は解群の群代数の適当な商であることを示す。 また、線形制約系ゲームは、線形系によってパラメータ化されたグラフの対上のグラフ同型ゲームと等価であることを示す。
  論文  参考訳（メタデータ） (2020-07-06T14:31:59Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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