Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Zyablov Bound:
TR07-109 | 7th October 2007
Venkatesan Guruswami, Atri Rudra

Better Binary List-Decodable Codes via Multilevel Concatenation

We give a polynomial time construction of binary codes with the best
currently known trade-off between rate and error-correction
radius. Specifically, we obtain linear codes over fixed alphabets
that can be list decoded in polynomial time up to the so called
Blokh-Zyablov bound. Our work ... more >>>

TR09-001 | 26th November 2008
Venkatesan Guruswami

Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes

Algebraic codes that achieve list decoding capacity were recently
constructed by a careful ``folding'' of the Reed-Solomon code. The
``low-degree'' nature of this folding operation was crucial to the list
decoding algorithm. We show how such folding schemes conducive to list
decoding arise out of the Artin-Frobenius automorphism at primes ... more >>>

TR15-110 | 8th July 2015
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

An error correcting code is said to be \emph{locally testable} if
there is a test that checks whether a given string is a codeword,
or rather far from the code, by reading only a small number of symbols
of the string. Locally testable codes (LTCs) are both interesting
in their ... more >>>

ISSN 1433-8092 | Imprint