All reports by Author Mary Wootters:

__
TR20-162
| 7th November 2020
__

Dean Doron, Mary Wootters#### High-Probability List-Recovery, and Applications to Heavy Hitters

Revisions: 3

__
TR20-013
| 17th February 2020
__

Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor#### Linear-time Erasure List-decoding of Expander Codes

Revisions: 1

__
TR19-122
| 13th September 2019
__

Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters#### LDPC Codes Achieve List-Decoding Capacity

Revisions: 3

__
TR18-091
| 4th May 2018
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

Revisions: 2

__
TR17-104
| 13th June 2017
__

Brett Hemenway, Noga Ron-Zewi, Mary Wootters#### Local List Recovery of High-rate Tensor Codes & Applications

Revisions: 1

__
TR14-104
| 9th August 2014
__

Atri Rudra, Mary Wootters#### It'll probably work out: improved list-decoding through random operations

__
TR13-140
| 8th October 2013
__

Atri Rudra, Mary Wootters#### Every list-decodable code for high noise has abundant near-optimal rate puncturings

__
TR11-118
| 6th September 2011
__

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters#### Public Key Locally Decodable Codes with Short Keys

Dean Doron, Mary Wootters

An error correcting code $\mathcal{C} \colon \Sigma^k \to \Sigma^n$ is list-recoverable from input list size $\ell$ if for any sets $\mathcal{L}_1, \ldots, \mathcal{L}_n \subseteq \Sigma$ of size at most $\ell$, one can efficiently recover the list $\mathcal{L} = \{ x \in \Sigma^k : \forall j \in [n], \mathcal{C}(x)_j \in \mathcal{L}_j ... more >>>

Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an inner code $\cC_0$ of length $d$, and a $d$-regular bipartite expander graph $G$ with $n$ vertices on each side, we give an algorithm to list-decode the expander code $\cC ... more >>>

Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. ... more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions ... more >>>

Brett Hemenway, Noga Ron-Zewi, Mary Wootters

In this work, we give the first construction of {\em high-rate} locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block.

In particular, our construction gives the first {\em capacity-achieving} locally list-decodable ...
more >>>

Atri Rudra, Mary Wootters

In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code.

The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural ...
more >>>

Atri Rudra, Mary Wootters

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

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

This work considers locally decodable codes in the computationally bounded channel model. The computationally bounded channel model, introduced by Lipton in 1994, views the channel as an adversary which is restricted to polynomial-time computation. Assuming the existence of IND-CPA secure public-key encryption, we present a construction of public-key locally decodable ... more >>>