Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with error-corecting codes:
TR11-165 | 8th December 2011
Elena Grigorescu, Chris Peikert

List Decoding Barnes-Wall Lattices

Revisions: 2

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in $R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>>

TR19-090 | 27th June 2019
Ronen Shaltiel, Swastik Kopparty, Jad Silbak

Quasilinear time list-decodable codes for space bounded channels

Revisions: 1

We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>>

ISSN 1433-8092 | Imprint