4 papers · 1 filter
Binary code rate bounds via classical--quantum channels
Omar Alrabiah, Venkatesan Guruswami
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one…
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
Omar Alrabiah, Venkatesan Guruswami
We prove that a binary linear code of block length that is locally correctable with queries against a fraction of adversarial errors must have dimension at most $O_δ…
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
Omar Alrabiah, Venkatesan Guruswami, Ray Li
A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate codes are not list-decodable using list-size beyond an error…
Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami +2
Reed-Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field element…