Strengthening Recursive Constructions for Zero-Error Shannon Capacity

2026-08-31 · Ravi Tandon arxiv

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.

📄 PDF Abstract BibTeX arXiv:2608.30273

Code (0)

등록된 구현이 없습니다.

Improved lower bounds for the Shannon capacity of odd cycles

2026-07-23 · Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman arxiv

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 th…

AI Uncertainty Based on Rademacher Complexity and Shannon Entropy

2021-02-12 · Mingyong Zhou

In this paper from communication channel coding perspective we are able to present both a theoretical and practical discussion of AI's uncertainty, capacity and evolution for pattern classification based on the classical…

Classification General Classification

Causal Transformers Perform Below Chance on Recursive Nested Constructions, Unlike Humans

2021-10-14 · Yair Lakretz, Théo Desbordes, Dieuwke Hupkes, Stanislas Dehaene

Recursive processing is considered a hallmark of human linguistic abilities. A recent study evaluated recursive processing in recurrent neural language models (RNN-LMs) and showed that such models perform below chance le…

Recursive Reinforcement Learning

2022-06-23 · Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi 외

Recursion is the fundamental paradigm to finitely describe potentially infinite objects. As state-of-the-art reinforcement learning (RL) algorithms cannot directly reason about recursion, they must rely on the practition…

Ingenuity Q-Learning reinforcement-learning Reinforcement Learning+1

Recursive Least Squares with Fading Regularization for Finite-Time Convergence without Persistent Excitation

2025-01-08 · Brian Lai, Dimitra Panagou, Dennis S. Bernstein

This paper extends recursive least squares (RLS) to include time-varying regularization. This extension provides flexibility for updating the least squares regularization term in real time. Existing results with constant…

parameter estimation