6 citations · 10 across the 10 of their papers we have counts for
18 papers
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 …
A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes
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,…
Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma
A binary code Enc is -list decodable if for all , the set List of all messages such that the relative H…
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…
Finer-grained Reductions in Fine-grained Hardness of Approximation
Elie Abboud, Noga Ron-Zewi
We investigate the relation between and required for obtaining a -approximation in time for closest pair problems under various distance metrics, and for o…
Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf
In this note, we give very simple constructions of unique neighbor expander graphs starting from spectral or combinatorial expander graphs of mild expansion. These constructions an…
Efficient List-Decoding with Constant Alphabet and List Sizes
Zeyu Guo, Noga Ron-Zewi
We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for a…
Locally testable codes via high-dimensional expanders
Yotam Dikstein, Irit Dinur, Prahladh Harsha +1
Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are "far" from all codewords by probing a giv…
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…
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi +1
In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query co…
Sampling-based proofs of almost-periodicity results and algorithmic applications
Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani +1
We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask, whose almost-periodicity lemma has h…
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…
An additive combinatorics approach to the log-rank conjecture in communication complexity
Eli Ben-Sasson, Shachar Lovett, Noga Zewi
For a -valued matrix let denote the deterministic communication complexity of the boolean function associated with . The log-rank conjecture of Lovász…