Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALGORITHMIC CODING THEORY:
Reports tagged with algorithmic coding theory:
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 >>>

TR20-142 | 15th September 2020
Locally decodable codes (LDCs) are error-correcting codes $C : \Sigma^k \to \Sigma^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off ... more >>>