All reports by Author Andrii Riazanov:

__
TR19-154
| 6th November 2019
__

Venkatesan Guruswami, Andrii Riazanov, Min Ye#### Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity

Revisions: 3

__
TR18-096
| 13th May 2018
__

Venkatesan Guruswami, Andrii Riazanov#### Beating Fredman-Komlós for perfect $k$-hashing

Venkatesan Guruswami, Andrii Riazanov, Min Ye

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

Venkatesan Guruswami, Andrii Riazanov

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is ... more >>>