Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets

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 elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a fundamental question in coding theory is determining if Reed-Solomon codes can optimally achieve list-decoding capacity. A recent breakthrough by Brakensiek, Gopi, and Makam established that Reed-Solomon codes are combinatorially list-decodable all the way to capacity. However, their results hold for randomly-punctured Reed-Solomon codes over an exponentially large field size 2O(n), where n is the block length of the code. A natural question is whether Reed-Solomon codes can still achieve capacity over smaller fields. We show that Reed-Solomon codes are list-decodable to capacity with linear field size O(n), which is evidently optimal up to a constant factor. Our techniques also show that random linear codes are list-decodable up to capacity with optimal list-size O(1/varepsilon) and near-optimal alphabet size 2O(1/varepsilon2), where varepsilon is the gap to capacity. As far as we are aware, list-decoding up to capacity with optimal list-size O(1/varepsilon) was not known to be achievable with any linear code over a constant alphabet size (even non-constructively), and it was also not known to be achievable for random linear codes over any alphabet size. With our proof, which maintains a hypergraph perspective of the list-decoding problem, we include an alternate presentation of ideas from Brakensiek, Gopi, and Makam that more directly connects the list-decoding problem to the GM-MDS theorem via a hypergraph orientation theorem.