1 citations · 2 across the 9 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.CC2023
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari +1
A code is a -locally decodable code (-LDC) if one can recover any chosen bit of the message with good confidence by…
cs.IT2023★ 1 cited
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…
cs.IT2023★ 1 cited
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…