6 citations · 10 across the 10 of their papers we have counts for
10 papers · 1 filter
Time- and Space-Efficient List Decoding up to Capacity
Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters
In the theory of error correcting codes, list-decoding refers to the following problem. Given a code and a received word , find all codewords …
Zero-knowledge and Quantum CSS Codes Are Equivalent
Noga Ron-Zewi, Mor Weiss
Zero-knowledge codes, introduced by Decatur, Goldreich, and Ron (ePrint 1997), are error-correcting codes in which few codeword symbols reveal no information about the encoded mess…
Advances in List Decoding of Polynomial Codes
Mrinal Kumar, Noga Ron-Zewi
Error-correcting codes are a method for representing data, so that one can recover the original information even if some parts of it were corrupted. The basic idea, which dates bac…
Efficient Decoding of Double-circulant and Wozencraft Codes from Square-root Errors
Oren Dubin, Noam Oz, Noga Ron-Zewi
We present efficient decoding algorithms from square-root errors for two known families of double-circulant codes: A construction based on Sidon sets (Bhargava, Taveres, and Shiva,…
Efficient List-decoding of Polynomial Ideal Codes with Optimal List Size
Noga Ron-Zewi, S. Venkitesh, Mary Wootters
In a recent breakthrough [BGM23, GZ23, AGL23], it was shown that randomly punctured Reed-Solomon codes are list decodable with optimal list size with high probability, i.e., they a…
Linear-time Erasure List-decoding of Expander Codes
Noga Ron-Zewi, Mary Wootters, Gilles Zémor
We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let be any integer. Given an inner code of length , and a -regular bip…
LDPC Codes Achieve List Decoding Capacity
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi +2
We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have…
Improved decoding of Folded Reed-Solomon and Multiplicity Codes
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf +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 ove…
Local List Recovery of High-rate Tensor Codes and Applications
Brett Hemenway, Noga Ron-Zewi, Mary Wootters
In this work, we give the first construction of high-rate locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motiva…
A new upper bound on the query complexity for testing generalized Reed-Muller codes
Noga Ron-Zewi, Madhu Sudan
Over a finite field $\F_q$ the -Reed-Muller code is the code given by evaluations of -variate polynomials of total degree at most on all points (of $\F_q^n$). The t…