Venkatesan Guruswami, Venkatesan Guruswami

Much progress has been made on decoding algorithms for

error-correcting codes in the last decade. In this article, we give an

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

Venkatesan Guruswami, Adam Smith

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

Venkatesan Guruswami, Patrick Xia

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

Venkatesan Guruswami, Ameya Velingker

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