Let$W$be a binary-input memoryless symmetric (BMS) channel with Shannon capacity$I(W)$and fix any$\alpha > 0$. We construct, for any sufficiently small$\delta > 0$, binary linear codes of block length$O(1/\delta ^{2+\alpha })$and rate$I(W)-\delta $that enable reliable communication on$W$with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established theexistenceof such codes (without efficient constructions or decoding) with block length$O(1/\delta ^{2})$. This quadratic dependence on the gap$\delta $to capacity is known to be best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Arıkan’s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.

The Shannon capacity of a graph is a fundamental quantity in zero-error information theory measuring the rate of growth of independent sets in graph powers. Despite being well-studied, this quantity continues to hold several mysteries. Lovász famously proved that the Shannon capacity of$C$5(the 5-cycle) is at most$\sqrt{5}$via his theta function. This bound is achieved by a simple linear code over$\mathbb{F}_{5}$mapping x → 2x. This motivates the notion of linear Shannon capacity of graphs, which is the largest rate achievable when restricting oneself to linear codes. We give a simple proof based on the polynomial method that the linear Shannon capacity of$C$5is$\sqrt{5}$. Our method applies more generally to Cayley graphs over the additive group of finite fields$\mathbb{F}_{q}$, giving an upper bound on the linear Shannon capacity. We compare this bound to the Lovász theta function, showing that they match for self-complementary Cayley graphs (such as C5), and that the bound is smaller in some cases. We also exhibit a quadratic gap between linear and general Shannon capacity for some graphs.

We revisit the linear programming bounds for the size vs. distance trade-off for binary codes, focusing on the bounds for the almost-balanced case, when all pairwise distances are between$d$and$n-d$, where$d$is the code distance and$n$is the block length. We give an optimal solution to Delsarte's LP for the almost-balanced case with large distance$d\geq(n-\sqrt{n})/2+1$, which shows that the optimal value of the LP coincides with the Grey-Rankin bound for self-complementary codes. We also show that a limitation of the asymptotic LP bound shown by Samorodnitsky, namely that it is at least the average of the first MRRW upper bound and Gilbert-Varshamov bound, continues to hold for the almost-balanced case.

Let W be a binary-input memoryless symmetric (BMS) channel with Shannon capacity I(W) and fix any α > 0. We construct, for any sufficiently small δ > 0, binary linear codes of block length O(1/δ2+α) and rate I(W)−δ that enable reliable communication on W with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with block length O(1/δ2). This quadratic dependence on the gap δ to capacity is known to be the best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the binary erasure channel.