Fugu-MT 論文翻訳(概要): Strengthening Recursive Constructions for Zero-Error Shannon Capacity

論文の概要: Strengthening Recursive Constructions for Zero-Error Shannon Capacity

arxiv url: http://arxiv.org/abs/2608.30273v1
Date: Mon, 31 Aug 2026 05:38:05 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-01 18:31:31.245246
Title: Strengthening Recursive Constructions for Zero-Error Shannon Capacity
Title（参考訳）: ゼロエラーシャノンキャパシティのための再帰構造強化
Abstract要約: 正確なシャノン容量は、5サイクルのC_5$を超える全ての奇数サイクルについて不明であり、奇数サイクルはゼロエラー情報理論において中心的な問題となる。最近のAI支援作業は、急速に改善されている。我々は、$C_7boxtimes 500$ yielding $(C_7)ge 3.25883262ldots$の独立集合を取得し、最もよく知られた下界を改善する。
参考スコア（独自算出の注目度）: 6.903959267723045
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The exact Shannon capacity is unknown for every odd cycle beyond the five-cycle $C_5$, making odd cycles a central open problem in zero-error information theory. Improving the known lower bounds requires constructing large independent sets in strong powers of these graphs. Recent AI-assisted work has produced a rapid sequence of improvements: building on the construction of Itty et al., Gao developed a recursive product construction for combining structured independent sets, and Buys, Polak, and Zuiddam (BPZ) subsequently strengthened this through a richer recursion framework. We continue this line of AI-assisted exploration and introduce a heterogeneous refinement of these constructions. The central observation is that the usefulness of an intermediate construction depends not only on the size of its current main independent set, but also on the auxiliary structure it carries into subsequent recursion. Consequently, different parts of that auxiliary structure need not use the same independent set, and different occurrences in a recursion need not use the same intermediate representation. We formalize this for Gao's binary product and derive explicit propagation rules showing how heterogeneous choices strengthen the resulting gadget while leaving its current code size unchanged, then extend the principle to the more general BPZ framework, tailoring constructions to the distinct roles they play within the recursion. Applying these refinements to the seven-cycle $C_7$, we obtain an independent set in $C_7^{\boxtimes 500}$ yielding $Θ(C_7)\ge 3.25883262\ldots$, improving the best known lower bound. Beyond the numerical gain, the results illustrate a general principle for recursive zero-error constructions: intermediate structures with the same dimension and current code size can have different downstream value depending on where and how they are used in the recursion.
Abstract（参考訳）: シャノンの正確な容量は、5サイクルのC_5$を超える全ての奇数サイクルについて不明であり、奇数サイクルはゼロエラー情報理論において中心的な問題となる。既知の下界を改善するためには、これらのグラフの強い力で大きな独立集合を構築する必要がある。近年のAI支援研究は、Itty et al の構築に基づいて、構造化された独立集合を組み合わせた再帰的製品構築を開発し、その後、よりリッチな再帰フレームワークによって、Buys, Polak, Zuiddam (BPZ) がこれを強化した。我々は、このAI支援探査のラインを継続し、これらの構造を不均一に改良する。中心的な観察は、中間構造の有用性は、現在の主独立集合のサイズだけでなく、その後の再帰をもたらす補助構造にも依存するということである。したがって、その補助構造の異なる部分は、同じ独立集合を使用する必要はなく、再帰における異なる発生は、同じ中間表現を使用する必要がなくなる。我々はこれをGaoのバイナリ製品に形式化し、現在のコードサイズをそのままにして、不均一な選択が生成ガジェットをどのように強化するかを示す明示的な伝搬ルールを導出し、その原則をより一般的なBPZフレームワークに拡張し、再帰の中でそれらが果たす異なる役割に構造を調整します。これらの改良を 7 サイクルの $C_7$ に適用すると、$C_7^{\boxtimes 500}$ の独立集合が$(C_7)\ge 3.25883262\ldots$ となり、最もよく知られた下界が改善される。数値的なゲインの他に、この結果は再帰的ゼロエラー構築の一般的な原理を示している:同じ次元と現在のコードサイズを持つ中間構造は、再帰にどのように使われるかによって、下流の値が異なる可能性がある。

関連論文リスト

"More Is Different'' in Neural Circuits: Algebraic Emergence of Effective Theories in Canonical Recurrent Motifs of Biological Neuronal Networks [0.0]
我々は、カノニカルニューラルネットワークのモチーフとその構成を有限変換系として表現する。入力条件の更新によって生成される遷移モノイドを解析する。
論文参考訳（メタデータ） (2026-08-31T04:36:37Z)
Imputation Meets Clustering: Exploiting Latent Subgroup Structure for Missing Data Recovery [52.29866804948133]
本稿では、クラスタリングと命令を相互に強化する共最適化プロセスとして再構築するフレームワークであるCAGI(Cluster-Aware Generative Imputation)を提案する。 14のベンチマークデータセットと15の代表的なベースラインの実験は、CAGIの優位性を実証している。
論文参考訳（メタデータ） (2026-07-08T02:50:02Z)
A Unified Framework for Structure-Aware Clustering and Heterogeneous Causal Graph Learning [2.8350191976016768]
複雑なシステムでは、相互作用変数は依存構造によって定義され、しばしば非巡回グラフとして符号化される。依存構造は対象によって異なり、この構造バイアスを無視し、サブポピュレーションを曖昧にする。本稿では,クラスタ固有の依存性構造を学習する構造方程式モデリング(Structure Equation Modeling, SEM)に基づく統合フレームワークを提案する。本手法は,クラスタ固有の因果依存性構造を高い正の確率と低い偽発見率で復元する。
論文参考訳（メタデータ） (2026-05-19T03:48:54Z)
Recursive Multi-Agent Systems [106.82473907888497]
本稿では,マルチエージェントフレームワークであるRecursiveMASを紹介する。 RecursiveMASは、軽量なRecursiveLinkモジュールを介して、異種エージェントを協調ループとして接続する。実行時複雑性と学習力学の理論解析により、RecursiveMASは標準テキストベースMASよりも効率的であることが判明した。
論文参考訳（メタデータ） (2026-04-28T17:59:34Z)
RiboSphere: Learning Unified and Efficient Representations of RNA Structures [57.40815107640066]
RNAのバックボーンは非常に柔軟で、非カノニカル相互作用が一般的であり、実験的に決定された3D構造は比較的少ない。本稿では,ベクトル量子化とフローマッチングを組み合わせることで,RNAの固有な幾何学的表現を学習するフレームワークであるemphRiboSphereを紹介する。
論文参考訳（メタデータ） (2026-03-20T04:36:35Z)
Functorial Neural Architectures from Higher Inductive Types [5.076419064097734]
ニューラルネットワークは構成一般化において体系的に失敗することを示す。この失敗はアーキテクチャであり、構成的一般化はデコーダの函手性と同値である。独立に生成したセグメントの構造連結によって構成されたデコーダが厳密なモノイド関手であることを証明した。
論文参考訳（メタデータ） (2026-03-17T05:08:30Z)
Wave-Attractor-Tree: A Hierarchical Binary Tree Reduction Architecture for Efficient Sequence Modeling [0.0]
作業は階層的なバイナリツリーベースのリダクションを導入し、通常の自己アテンションを置き換える。このモデルは、コンバージェンス速度と長距離構造上の依存関係の精度の両方において、標準トランスフォーマーを著しく上回っている。
論文参考訳（メタデータ） (2026-02-28T21:17:27Z)
ProtInvTree: Deliberate Protein Inverse Folding with Reward-guided Tree Search [77.55575655986252]
ProtInvTreeはタンパク質逆フォールディングのための報酬誘導ツリー検索フレームワークである。シークエンス生成は、意図的に、ステップワイズな意思決定プロセスとして再構成される。検索深度と幅を広げて、再トレーニングすることなく、フレキシブルなテストタイムスケーリングをサポートする。
論文参考訳（メタデータ） (2025-06-01T09:34:20Z)
On the Expressive Power of Tree-Structured Probabilistic Circuits [8.160496835449157]
我々は、$n$変数に対して、同じ確率分布を計算する同値木の大きさに準多項式上界$nO(log n)$が存在することを示す。また,木面の深さ制限を考慮すれば,木面とDAG構造PCとの間には超ポリノミカルな分離が存在することを示す。
論文参考訳（メタデータ） (2024-10-07T19:51:30Z)
Differentiable and Transportable Structure Learning [73.84540901950616]
本稿では,新しいアーキテクチャと損失関数により,発見された構造物の輸送性を回復するD-Structを紹介する。 D-Structは依然として微分可能であるため、既存の微分可能アーキテクチャでは容易に適用できる。
論文参考訳（メタデータ） (2022-06-13T17:50:53Z)
Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
論文参考訳（メタデータ） (2021-06-02T01:37:52Z)

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

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