9 citations · 17 across the 6 of their papers we have counts for
5 papers · 1 filter
Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields
Minshen Zhu
Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenom…
Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
Alexander R. Block, Jeremiah Blocki, Kuan Cheng +4
Locally Decodable Codes (LDCs) are error-correcting codes encoding \emph{messages} in to \emph{codewords} in , with super-fast decoding algo…
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
Kuan Cheng, Elena Grigorescu, Xin Li +2
The goal of the trace reconstruction problem is to recover a string given many independent {\em traces} of , where a trace is a subsequence obtained from deletin…
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
Alex Block, Jeremiah Blocki, Kuan Cheng +4
Locally Decodable Codes (LDCs) are error-correcting codes with super-fast decoding algorithms. They are important mathematical objects in many areas of theor…
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu +3
Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have…