Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MARY WOOTTERS:
All reports by Author Mary Wootters:

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

Improved decoding of Folded Reed-Solomon and Multiplicity Codes

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