35 citations · 159 across the 35 of their papers we have counts for
9 papers · 1 filter
Amortized Relaxed Locally Decodable Codes
Jeremiah Blocki, Justin Zhang
Locally decodable codes (LDCs) enable recovery of any message symbol by probing only a small number of positions in a possibly corrupted codeword. The central parameters of an LDC…
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…
Amortized Locally Decodable Codes for Insertions and Deletions
Jeremiah Blocki, Justin Zhang
Locally Decodable Codes (LDCs) are error correcting codes which permit the recovery of any single message symbol with a low number of queries to the codeword (the locality). Tradit…
Amortized Locally Decodable Codes
Jeremiah Blocki, Justin Zhang
Locally Decodable Codes (LDCs) are error correcting codes that admit efficient decoding of individual message symbols without decoding the entire message. Unfortunately, known LDC…
Computationally Relaxed Locally Decodable Codes, Revisited
Alexander R. Block, Jeremiah Blocki
We revisit computationally relaxed locally decodable codes (crLDCs) (Blocki et al., Trans. Inf. Theory '21) and give two new constructions. Our first construction is a Hamming crLD…
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…