Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR20-013 | 17th February 2020
Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor

Linear-time Erasure List-decoding of Expander Codes

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

TR19-122 | 13th September 2019
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters

LDPC Codes Achieve List-Decoding Capacity

Revisions: 2

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

TR18-091 | 4th May 2018
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

Improved decoding of Folded Reed-Solomon and Multiplicity Codes

Revisions: 1

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

TR17-104 | 13th June 2017
Brett Hemenway, Noga Ron-Zewi, Mary Wootters

Local List Recovery of High-rate Tensor Codes & Applications

Revisions: 1

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

TR14-104 | 9th August 2014
Atri Rudra, Mary Wootters

It'll probably work out: improved list-decoding through random operations

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

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

TR11-118 | 6th September 2011
Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

Public Key Locally Decodable Codes with Short Keys

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

ISSN 1433-8092 | Imprint