Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with polar codes:
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 >>>

TR18-027 | 8th February 2018
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

General Strong Polarization

Revisions: 1

Ar\i kan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix $M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the $\textit{polarization}$ of an associated $[0,1]$-bounded martingale, ... more >>>

ISSN 1433-8092 | Imprint