論文の概要: Improved lower bounds for the Shannon capacity of odd cycles

• arxiv url: http://arxiv.org/abs/2607.21517v2
• Date: Thu, 30 Jul 2026 17:24:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 15:03:14.02063
• Title: Improved lower bounds for the Shannon capacity of odd cycles
• Title（参考訳）: 奇数周期のシャノン容量に対する下界の改善
• Authors: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman,
• Abstract要約: グラフのシャノン容量$(G)$は、情報を伝達できる最大レートを定量化する。 我々は、C_710$で134753$、C_116$で21909ドル、C_136$で62530$、80769741/8>7.301399$で独立したセットを構築する。
• 参考スコア（独自算出の注目度）: 2.846561253333858
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Shannon capacity $Θ(G)$ of a graph $G$ quantifies the maximum rate at which information can be transmitted with zero error over a noisy channel. It is lower bounded by $α(G^d)^{1/d}$ for any $d$, where $α(G^d)$ is the independence number of the $d$-th strong product of $G$. We construct independent sets of size $134753$ in $C_7^{10}$, $21909$ in $C_{11}^{6}$, $62530$ in $C_{13}^{6}$, and $8076974$ in $C_{15}^{8}$, improving the best known lower bounds for the Shannon capacity of these graphs to $Θ(C_7)\geq 134753^{1/10}>3.258020$, $Θ(C_{11})\geq 21909^{1/6}>5.289773$, $Θ(C_{13})\geq 62530^{1/6}>6.300109$, and $Θ(C_{15})\geq 8076974^{1/8}>7.301399$. We also improve the best known lower bounds on the independence numbers of several individual strong products of odd cycles that do not improve the Shannon capacity lower bound. The constructions were discovered through iterative interactions with a Large Language Model (LLM), illustrating the potential of LLMs for finding explicit combinatorial constructions.
• Abstract（参考訳）: グラフ$G$のシャノンキャパシティ$(G)$は、ノイズのあるチャネル上でゼロエラーで情報を伝達できる最大レートを定量化する。 任意の$d$に対して$α(G^d)^{1/d}$で下界されるが、$α(G^d)$は$G$の$d$-番目の強積の独立数である。 我々は、サイズ $134753$ in $C_7^{10}$, $21909$ in $C_{11}^{6}$, 6,2530$ in $C_{13}^{6}$, 8,076974$ in $C_{15}^{8}$, and improve the most known lower bounds for the Shannon capacity of these graphs of these graphs to $s(C_7)\geq 134753^{1/10}>3.258020$, $s(C_{11})\geq 21909^{1/6}>5.289773$, $s(C_{13})\geq 62530^{1/6}>6.300109$, and $s(C_{15})\geq 809797^{1/7}$.999999となる。 また、シャノンのキャパシティの低いバウンドを改善しない奇周期のいくつかの個々の強い積の独立性に関する最もよく知られた下界も改善する。 これらの構造は、LLM(Large Language Model)との反復的な相互作用を通じて発見され、明示的な組合せ構造を見つけるためのLLMの可能性を示した。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Asymptotic Gate Count Bounds for Ancilla-Free Single-Qubit Synthesis with Arithmetic Gates [0.0]
  単一キュービットユニタリのアンシラフリー近似について、Clifford+$G$上のゲート列によるUin rm SU(2)$について検討する。 近似誤差を最大$varepsilon$で達成するために必要となる最小$G$-countの3つの境界を証明します。
  論文  参考訳（メタデータ） (2025-10-08T23:48:48Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Learning junta distributions, quantum junta states, and QAC$^0$ circuits [0.0]
  本稿では, 量子分布(量子ユンタ状態)と$mathsfQAC0$回路の学習問題を考察する。 例えば$n$-qubit $mathsfQAC0$の回路は$s$、deep $d$、$a$の補助キュービットは2O(log(s22a)d)log (n)$のChoi状態のコピーから学習可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-21T09:39:20Z)
• Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
  Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2023-02-07T22:58:12Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Improved upper bounds on the stabilizer rank of magic states [0.0]
  改良は、マジック状態 $|Trangle=sqrt2-1(|0rangle+eipi/4|1rangle)$ の安定化ランクに $m$ の上限で新しい上限を設定することで得られる。 Clifford ゲートと$m$のインスタンスからなる回路に対して,実行時 $textpoly(n,m) 2m/2$ のシングルキュービット $Z$-rotation ゲートの強いシミュレーションアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-06-14T20:20:51Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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