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