5 papers · 1 filter
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…
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…
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…