Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SHANNON CAPACITY:
Reports tagged with Shannon capacity:
TR06-123 | 15th September 2006
Venkatesan Guruswami, Venkatesan Guruswami

#### Iterative Decoding of Low-Density Parity Check Codes (A Survey)

Much progress has been made on decoding algorithms for
introduction to some fundamental results on iterative, message-passing
algorithms for low-density parity check codes. For certain
important stochastic channels, this line of work has enabled getting
very close to ... more >>>

TR10-077 | 26th April 2010

#### Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently ... more >>>

TR13-050 | 1st April 2013
Venkatesan Guruswami, Patrick Xia

#### Polar Codes: Speed of polarization and polynomial gap to capacity

Revisions: 1

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within $\epsilon > 0$ of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in $1/\epsilon$. Polar coding gives the *first known explicit construction* with rigorous ... more >>>

TR14-165 | 3rd December 2014
Venkatesan Guruswami, Ameya Velingker

#### An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets

We prove a lower estimate on the increase in entropy when two copies of a conditional random variable $X | Y$, with $X$ supported on $\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$. Specifically, given two i.i.d. copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of random variables $(X,Y)$, with $X$ ... more >>>

ISSN 1433-8092 | Imprint