Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CHAINING ARGUMENT:
Reports tagged with Chaining argument:
TR13-140 | 8th October 2013
Atri Rudra, Mary Wootters

#### Every list-decodable code for high noise has abundant near-optimal rate puncturings

We show that any $q$-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius $1 - 1/q - \epsilon$ with near-optimal rate and list sizes.

Our results imply that most" Reed-Solomon codes are list decodable ... more >>>

TR18-116 | 18th June 2018
Xue Chen, David Zuckerman

#### Existence of Simple Extractors

Revisions: 1

We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of \$\tilde{O}(n ... more >>>

ISSN 1433-8092 | Imprint