Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ANDRII RIAZANOV:
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

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


TR18-096 | 13th May 2018
Venkatesan Guruswami, Andrii Riazanov

Beating Fredman-Komlós for perfect k-hashing

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




ISSN 1433-8092 | Imprint