Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
List decoding
open-in-new
<h2 id="mathematical-formulation">Mathematical formulation</h2> <p>Let C {\displaystyle {\mathcal {C}}} be a ( n , k , d ) q {\displaystyle (n,k,d)_{q}} error-correcting code; in other words, C {\displaystyle {\mathcal {C}}} is a code of length n {\displaystyle n} , dimension k {\displaystyle k} and minimum distance d {\displaystyle d} over an alphabet Σ {\displaystyle \Sigma } of size q {\displaystyle q} . The list-decoding problem can now be formulated as follows: </p><p>Input: Received word x ∈ Σ n {\displaystyle x\in \Sigma ^{n}} , <a href="/facts/Error_bound/orSvvIMC">error bound</a> e {\displaystyle e} </p><p>Output: A list of all codewords x 1 , x 2 , … , x m ∈ C {\displaystyle x_{1},x_{2},\ldots ,x_{m}\in {\mathcal {C}}} whose <a href="/facts/Hamming_distance/MgdtbYPo">hamming distance</a> from x {\displaystyle x} is at most e {\displaystyle e} . </p> <h2 id="motivation-for-list-decoding">Motivation for list decoding</h2> <p>Given a received word y {\displaystyle y} , which is a noisy version of some transmitted codeword c {\displaystyle c} , the decoder tries to output the transmitted codeword by placing its bet on a codeword that is “nearest” to the received word. The Hamming distance between two codewords is used as a metric in finding the nearest codeword, given the received word by the decoder. If d {\displaystyle d} is the minimum Hamming distance of a code C {\displaystyle {\mathcal {C}}} , then there exists two codewords c 1 {\displaystyle c_{1}} and c 2 {\displaystyle c_{2}} that differ in exactly d {\displaystyle d} positions. Now, in the case where the received word y {\displaystyle y} is equidistant from the codewords c 1 {\displaystyle c_{1}} and c 2 {\displaystyle c_{2}} , unambiguous decoding becomes impossible as the decoder cannot decide which one of c 1 {\displaystyle c_{1}} and c 2 {\displaystyle c_{2}} to output as the original transmitted codeword. As a result, the half-the minimum distance acts as a combinatorial barrier beyond which unambiguous error-correction is impossible, if we only insist on unique decoding. However, received words such as y {\displaystyle y} considered above occur only in the worst-case and if one looks at the way <a href="/facts/Hamming_ball/XXzf4UYm">Hamming balls</a> are packed in high-dimensional space, even for error patterns e {\displaystyle e} beyond half-the minimum distance, there is only a single codeword c {\displaystyle c} within Hamming distance e {\displaystyle e} from the received word. This claim has been shown to hold with high probability for a random code picked from a natural ensemble and more so for the case of <a href="/facts/Reed%25E2%2580%2593Solomon_error_correction/HPc3Qj6N">Reed–Solomon codes</a> which is well studied and quite ubiquitous in the real world applications. In fact, Shannon's proof of the capacity theorem for <i>q</i>-ary symmetric channels can be viewed in light of the above claim for random codes. </p><p>Under the mandate of list-decoding, for worst-case errors, the decoder is allowed to output a small list of codewords. With some context specific or side information, it may be possible to prune the list and recover the original transmitted codeword. Hence, in general, this seems to be a stronger error-recovery model than unique decoding. </p> <h2 id="list-decoding-potential">List-decoding potential</h2> <p>For a polynomial-time list-decoding algorithm to exist, we need the combinatorial guarantee that any Hamming ball of radius p n {\displaystyle pn} around a received word r {\displaystyle r} (where p {\displaystyle p} is the fraction of errors in terms of the block length n {\displaystyle n} ) has a small number of codewords. This is because the list size itself is clearly a lower bound on the running time of the algorithm. Hence, we require the list size to be a polynomial in the block length n {\displaystyle n} of the code. A combinatorial consequence of this requirement is that it imposes an upper bound on the rate of a code. List decoding promises to meet this upper bound. It has been shown non-constructively that codes of rate R {\displaystyle R} exist that can be list decoded up to a fraction of errors approaching 1 − R {\displaystyle 1-R} . The quantity 1 − R {\displaystyle 1-R} is referred to in the literature as the list-decoding capacity. This is a substantial gain compared to the unique decoding model as we now have the potential to correct twice as many errors. Naturally, we need to have at least a fraction R {\displaystyle R} of the transmitted symbols to be correct in order to recover the message. This is an information-theoretic lower bound on the number of correct symbols required to perform decoding and with list decoding, we can potentially achieve this information-theoretic limit. However, to realize this potential, we need explicit codes (codes that can be constructed in polynomial time) and efficient algorithms to perform encoding and decoding. </p> <h2 id="p-l-list-decodability">(<i>p</i>, <i>L</i>)-list-decodability</h2> <p>For any error fraction 0 ⩽ p ⩽ 1 {\displaystyle 0\leqslant p\leqslant 1} and an integer L ⩾ 1 {\displaystyle L\geqslant 1} , a code C ⊆ Σ n {\displaystyle {\mathcal {C}}\subseteq \Sigma ^{n}} is said to be list decodable up to a fraction p {\displaystyle p} of errors with list size at most L {\displaystyle L} or ( p , L ) {\displaystyle (p,L)} -list-decodable if for every y ∈ Σ n {\displaystyle y\in \Sigma ^{n}} , the number of codewords c ∈ C {\displaystyle c\in C} within Hamming distance p n {\displaystyle pn} from y {\displaystyle y} is at most L . {\displaystyle L.} </p> <h2 id="combinatorics-of-list-decoding">Combinatorics of list decoding</h2> <p>The relation between list decodability of a code and other fundamental parameters such as minimum distance and rate have been fairly well studied. It has been shown that every code can be list decoded using small lists beyond half the minimum distance up to a bound called the Johnson radius. This is quite significant because it proves the existence of ( p , L ) {\displaystyle (p,L)} -list-decodable codes of good rate with a list-decoding radius much larger than d 2 . {\displaystyle {\tfrac {d}{2}}.} In other words, the <a href="/facts/Johnson_bound/bCn73V5H">Johnson bound</a> rules out the possibility of having a large number of codewords in a Hamming ball of radius slightly greater than d 2 {\displaystyle {\tfrac {d}{2}}} which means that it is possible to correct far more errors with list decoding. </p> <h2 id="list-decoding-capacity">List-decoding capacity</h2> Theorem (List-Decoding Capacity). Let q ⩾ 2 , 0 ⩽ p ⩽ 1 − 1 q {\displaystyle q\geqslant 2,0\leqslant p\leqslant 1-{\tfrac {1}{q}}} and ϵ ⩾ 0. {\displaystyle \epsilon \geqslant 0.} The following two statements hold for large enough block length n {\displaystyle n} . i) If R ⩽ 1 − H q ( p ) − ϵ {\displaystyle R\leqslant 1-H_{q}(p)-\epsilon } , then there exists a ( p , O ( 1 / ϵ ) ) {\displaystyle (p,O(1/\epsilon ))} -list decodable code. ii) If R ⩾ 1 − H q ( p ) + ϵ {\displaystyle R\geqslant 1-H_{q}(p)+\epsilon } , then every ( p , L ) {\displaystyle (p,L)} -list-decodable code has L = q Ω ( n ) {\displaystyle L=q^{\Omega (n)}} . Where H q ( p ) = p log q ( q − 1 ) − p log q p − ( 1 − p ) log q ( 1 − p ) {\displaystyle H_{q}(p)=p\log _{q}(q-1)-p\log _{q}p-(1-p)\log _{q}(1-p)} is the q {\displaystyle q} -ary entropy function defined for p ∈ ( 0 , 1 ) {\displaystyle p\in (0,1)} and extended by continuity to [ 0 , 1 ] . {\displaystyle [0,1].} <p>What this means is that for rates approaching the channel capacity, there exists list decodable codes with polynomial sized lists enabling efficient decoding algorithms whereas for rates exceeding the channel capacity, the list size becomes exponential which rules out the existence of efficient decoding algorithms. </p><p>The proof for list-decoding capacity is a significant one in that it exactly matches the capacity of a q {\displaystyle q} -ary symmetric channel q S C p {\displaystyle qSC_{p}} . In fact, the term "list-decoding capacity" should actually be read as the capacity of an adversarial channel under list decoding. Also, the proof for list-decoding capacity is an important result that pin points the optimal trade-off between rate of a code and the fraction of errors that can be corrected under list decoding. </p> <h3>Sketch of proof</h3> <p>The idea behind the proof is similar to that of Shannon's proof for capacity of the <a href="/facts/Binary_symmetric_channel/bFPGGghC">binary symmetric channel</a> B S C p {\displaystyle BSC_{p}} where a random code is picked and showing that it is ( p , L ) {\displaystyle (p,L)} -list-decodable with high probability as long as the rate R ⩽ 1 − H q ( p ) − 1 L . {\displaystyle R\leqslant 1-H_{q}(p)-{\tfrac {1}{L}}.} For rates exceeding the above quantity, it can be shown that the list size L {\displaystyle L} becomes super-polynomially large. </p><p>A "bad" event is defined as one in which, given a received word y ∈ [ q ] n {\displaystyle y\in [q]^{n}} and L + 1 {\displaystyle L+1} messages m 0 , … , m L ∈ [ q ] k , {\displaystyle m_{0},\ldots ,m_{L}\in [q]^{k},} it so happens that C ( m i ) ∈ B ( y , p n ) {\displaystyle {\mathcal {C}}(m_{i})\in B(y,pn)} , for every 0 ⩽ i ⩽ L {\displaystyle 0\leqslant i\leqslant L} where p {\displaystyle p} is the fraction of errors that we wish to correct and B ( y , p n ) {\displaystyle B(y,pn)} is the Hamming ball of radius p n {\displaystyle pn} with the received word y {\displaystyle y} as the center. </p><p>Now, the probability that a codeword C ( m i ) {\displaystyle {\mathcal {C}}(m_{i})} associated with a fixed message m i ∈ [ q ] k {\displaystyle m_{i}\in [q]^{k}} lies in a Hamming ball B ( y , p n ) {\displaystyle B(y,pn)} is given by </p> Pr [ C ( m i ) ∈ B ( y , p n ) ] = V o l q ( y , p n ) q n ⩽ q − n ( 1 − H q ( p ) ) , {\displaystyle \Pr \left[C(m_{i})\in B(y,pn)\right]={\frac {\mathrm {Vol} _{q}(y,pn)}{q^{n}}}\leqslant q^{-n(1-H_{q}(p))},} <p>where the quantity V o l q ( y , p n ) {\displaystyle Vol_{q}(y,pn)} is the volume of a Hamming ball of radius p n {\displaystyle pn} with the received word y {\displaystyle y} as the center. The inequality in the above relation follows from the upper bound on the volume of a Hamming ball. The quantity q H q ( p ) {\displaystyle q^{H_{q}(p)}} gives a very good estimate on the volume of a Hamming ball of radius p {\displaystyle p} centered on any word in [ q ] n . {\displaystyle [q]^{n}.} Put another way, the volume of a Hamming ball is translation invariant. To continue with the proof sketch, we conjure the <a href="/facts/Union_bound/HDRr2yUH">union bound</a> in probability theory which tells us that the probability of a bad event happening for a given ( y , m 0 , … , m L ) {\displaystyle (y,m_{0},\dots ,m_{L})} is upper bounded by the quantity q − n ( L + 1 ) ( 1 − H q ( p ) ) {\displaystyle q^{-n(L+1)(1-H_{q}(p))}} . </p><p>With the above in mind, the probability of "any" bad event happening can be shown to be less than 1 {\displaystyle 1} . To show this, we work our way over all possible received words y ∈ [ q ] n {\displaystyle y\in [q]^{n}} and every possible subset of L {\displaystyle L} messages in [ q ] k . {\displaystyle [q]^{k}.} </p><p>Now turning to the proof of part (ii), we need to show that there are super-polynomially many codewords around every y ∈ [ q ] n {\displaystyle y\in [q]^{n}} when the rate exceeds the list-decoding capacity. We need to show that | C ∩ B ( y , p n ) | {\displaystyle |{\mathcal {C}}\cap B(y,pn)|} is super-polynomially large if the rate R ⩾ 1 − H q ( p ) + ϵ {\displaystyle R\geqslant 1-H_{q}(p)+\epsilon } . Fix a codeword c ∈ C {\displaystyle c\in {\mathcal {C}}} . Now, for every y ∈ [ q ] n {\displaystyle y\in [q]^{n}} picked at random, we have </p> Pr [ c ∈ B ( y , p n ) ] = Pr [ y ∈ B ( c , p n ) ] {\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]} <p>since Hamming balls are translation invariant. From the definition of the volume of a Hamming ball and the fact that y {\displaystyle y} is chosen uniformly at random from [ q ] n {\displaystyle [q]^{n}} we also have </p> Pr [ c ∈ B ( y , p n ) ] = Pr [ y ∈ B ( c , p n ) ] = V o l ( y , p n ) q n ⩾ q − n ( 1 − H q ( p ) ) − o ( n ) {\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]={\frac {\mathrm {Vol} (y,pn)}{q^{n}}}\geqslant q^{-n(1-H_{q}(p))-o(n)}} <p>Let us now define an indicator variable X c {\displaystyle X_{c}} such that </p> X c = { 1 c ∈ B ( y , p n ) 0 otherwise {\displaystyle X_{c}={\begin{cases}1&c\in B(y,pn)\\0&{\text{otherwise}}\end{cases}}} <p>Taking the expectation of the volume of a Hamming ball we have </p> E [ | B ( y , p n ) | ] = ∑ c ∈ C E [ X c ] = ∑ c ∈ C Pr [ X c = 1 ] ⩾ ∑ q − n ( 1 − H q ( p ) + o ( n ) ) = ∑ q n ( R − 1 + H q ( p ) + o ( 1 ) ) ⩾ q Ω ( n ) {\displaystyle {\begin{aligned}E[|B(y,pn)|]&=\sum _{c\in {\mathcal {C}}}E[X_{c}]\\[4pt]&=\sum _{c\in {\mathcal {C}}}\Pr[X_{c}=1]\\[4pt]&\geqslant \sum q^{-n(1-H_{q}(p)+o(n))}\\[4pt]&=\sum q^{n(R-1+H_{q}(p)+o(1))}\\[4pt]&\geqslant q^{\Omega (n)}\end{aligned}}} <p>Therefore, by the probabilistic method, we have shown that if the rate exceeds the list-decoding capacity, then the list size becomes super-polynomially large. This completes the proof sketch for the list-decoding capacity. </p> <h2 id="list-decodability-of-reed-solomon-codes">List decodability of <a href="/facts/Reed%25E2%2580%2593Solomon_error_correction/HPc3Qj6N">Reed-Solomon Codes</a></h2> <p>In 2023, building upon three seminal works,<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> coding theorists showed that, with high probability, <a href="/facts/Reed%25E2%2580%2593Solomon_error_correction/HPc3Qj6N">Reed-Solomon codes</a> defined over random evaluation points are list decodable up to the list-decoding capacity over linear size alphabets. </p> <h2 id="list-decoding-algorithms">List-decoding algorithms</h2> <p>In the period from 1995 to 2007, the coding theory community developed progressively more efficient list-decoding algorithms. Algorithms for <a href="/facts/Reed%25E2%2580%2593Solomon_error_correction/HPc3Qj6N">Reed–Solomon codes</a> that can decode up to the Johnson radius which is 1 − 1 − δ {\displaystyle 1-{\sqrt {1-\delta }}} exist where δ {\displaystyle \delta } is the normalised distance or relative distance. However, for Reed-Solomon codes, δ = 1 − R {\displaystyle \delta =1-R} which means a fraction 1 − R {\displaystyle 1-{\sqrt {R}}} of errors can be corrected. Some of the most prominent list-decoding algorithms are the following: </p> <ul><li>Sudan '95 – The first known non-trivial list-decoding algorithm for Reed–Solomon codes that achieved efficient list decoding up to 1 − 2 R {\displaystyle 1-{\sqrt {2R}}} errors developed by <a href="/facts/Madhu_Sudan/6XbwMvWN">Madhu Sudan</a>.</li> <li><a href="/facts/Guruswami%25E2%2580%2593Sudan_list_decoding_algorithm/xW1fh0oC">Guruswami–Sudan '98</a> – An improvement on the above algorithm for list decoding Reed–Solomon codes up to 1 − R {\displaystyle 1-{\sqrt {R}}} errors by Madhu Sudan and his then doctoral student <a href="/facts/Venkatesan_Guruswami/FLUy7glV">Venkatesan Guruswami</a>.</li> <li>Parvaresh–Vardy '05 – In a breakthrough paper, Farzad Parvaresh and <a href="/facts/Alexander_Vardy/WnHCCLgV">Alexander Vardy</a> presented codes that can be list decoded beyond the 1 − R {\displaystyle 1-{\sqrt {R}}} radius for low rates R {\displaystyle R} . Their codes are variants of Reed-Solomon codes which are obtained by evaluating m ⩾ 1 {\displaystyle m\geqslant 1} correlated polynomials instead of just 1 {\displaystyle 1} as in the case of usual Reed-Solomon codes.</li> <li>Guruswami–Rudra '06 - In yet another breakthrough, Venkatesan Guruswami and <a href="http://www.cse.buffalo.edu/~atri/">Atri Rudra</a> give explicit codes that achieve list-decoding capacity, that is, they can be list decoded up to the radius 1 − R − ϵ {\displaystyle 1-R-\epsilon } for any ϵ > 0 {\displaystyle \epsilon >0} . In other words, this is error-correction with optimal redundancy. This answered a question that had been open for about 50 years. This work has been invited to the Research Highlights section of the Communications of the ACM (which is “devoted to the most important research results published in Computer Science in recent years”) and was mentioned in an article titled “Coding and Computing Join Forces” in the Sep 21, 2007 issue of the Science magazine. The codes that they are given are called <a href="/facts/Folded_Reed%25E2%2580%2593Solomon_code/zUtEKxDL">folded Reed-Solomon codes</a> which are nothing but plain Reed-Solomon codes but viewed as a code over a larger alphabet by careful bundling of codeword symbols.</li></ul> <p>Because of their ubiquity and the nice algebraic properties they possess, list-decoding algorithms for Reed–Solomon codes were a main focus of researchers. The list-decoding problem for Reed–Solomon codes can be formulated as follows: </p><p>Input: For an [ n , k + 1 ] q {\displaystyle [n,k+1]_{q}} Reed-Solomon code, we are given the pair ( α i , y i ) {\displaystyle (\alpha _{i},y_{i})} for 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n} , where y i {\displaystyle y_{i}} is the i {\displaystyle i} th bit of the received word and the α i {\displaystyle \alpha _{i}} 's are distinct points in the finite field F q {\displaystyle F_{q}} and an error parameter e = n − t {\displaystyle e=n-t} . </p><p>Output: The goal is to find all the polynomials P ( X ) ∈ F q [ X ] {\displaystyle P(X)\in F_{q}[X]} of degree at most k {\displaystyle k} which is the message length such that p ( α i ) = y i {\displaystyle p(\alpha _{i})=y_{i}} for at least t {\displaystyle t} values of i {\displaystyle i} . Here, we would like to have t {\displaystyle t} as small as possible so that a greater number of errors can be tolerated. </p><p>With the above formulation, the general structure of list-decoding algorithms for Reed-Solomon codes is as follows: </p><p>Step 1: (Interpolation) Find a non-zero bivariate polynomial Q ( X , Y ) {\displaystyle Q(X,Y)} such that Q ( α i , y i ) = 0 {\displaystyle Q(\alpha _{i},y_{i})=0} for 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n} . </p><p>Step 2: (Root finding/Factorization) Output all degree k {\displaystyle k} polynomials p ( X ) {\displaystyle p(X)} such that Y − p ( X ) {\displaystyle Y-p(X)} is a factor of Q ( X , Y ) {\displaystyle Q(X,Y)} i.e. Q ( X , p ( X ) ) = 0 {\displaystyle Q(X,p(X))=0} . For each of these polynomials, check if p ( α i ) = y i {\displaystyle p(\alpha _{i})=y_{i}} for at least t {\displaystyle t} values of i ∈ [ n ] {\displaystyle i\in [n]} . If so, include such a polynomial p ( X ) {\displaystyle p(X)} in the output list. </p><p>Given the fact that bivariate polynomials can be factored efficiently, the above algorithm runs in polynomial time. </p> <h2 id="applications-in-complexity-theory-and-cryptography">Applications in complexity theory and cryptography</h2> <p>Algorithms developed for list decoding of several interesting code families have found interesting applications in <a href="/facts/Analysis_of_algorithms/pStoBgBn">computational complexity</a> and the field of <a href="/facts/Cryptography/e94PEVau">cryptography</a>. Following is a sample list of applications outside of coding theory: </p> <ul><li>Construction of <a href="/facts/Hard-core_predicate/jhThVcFC">hard-core predicates</a> from <a href="/facts/One-way_function/rGtcumDW">one-way permutations</a>.</li> <li>Predicting witnesses for NP-search problems.</li> <li>Amplifying hardness of Boolean functions.</li> <li>Average case hardness of <a href="/facts/Permanent_(mathematics)/eJWgdahx">permanent</a> of random matrices.</li> <li><a href="/facts/Extractor_(mathematics)/UC1j6bn9">Extractors</a> and <a href="/facts/Pseudorandom_generator/sdRrlm8Y">Pseudorandom generators</a>.</li> <li>Efficient traitor tracing.</li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Folded_Reed%25E2%2580%2593Solomon_code/zUtEKxDL">Folded Reed–Solomon code</a></li></ul> <p>Historical: </p><ul><li>Elias, Peter (1957). <a href="https://dspace.mit.edu/bitstream/handle/1721.1/4484/RLE-TR-335-04734756.pdf">"List decoding for noisy channels"</a> (PDF). <i>1957-IRE WESCON Convention Record, Pt. 2</i>. pp. 94–104.</li> <li>Wozencraft, J. M. (1958). "List decoding". <i>Quarterly Progress Report, Research Laboratory of Electronics, MIT</i>. 48: 90–95.</li></ul> <p>Review articles: </p> <ul><li>Elias, P. (1991-01). <a href="http://ieeexplore.ieee.org/document/61123/">"Error-correcting codes for list decoding"</a>. <i>IEEE Transactions on Information Theory</i>. 37 (1): 5–12. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2F18.61123">10.1109/18.61123</a>. {{cite journal}}: Check date values in: |date= (help)</li> <li>Sudan, Madhu (2000), van Leeuwen, Jan; Watanabe, Osamu; Hagiya, Masami; Mosses, Peter D. (eds.), <a href="http://link.springer.com/10.1007/3-540-44929-9_3">"List Decoding: Algorithms and Applications"</a>, <i>Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics</i>, vol. 1872, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 25–41, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-44929-9_3">10.1007/3-540-44929-9_3</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-67823-6, retrieved 2025-06-07</li> <li>Guruswami, Venkatesan (2005). <a href="http://link.springer.com/10.1007/b104335"><i>List Decoding of Error-Correcting Codes</i></a>. Lecture Notes in Computer Science. Vol. 3282. Berlin, Heidelberg: Springer Berlin Heidelberg. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fb104335">10.1007/b104335</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-24051-8.</li> <li>Guruswami, Venkatesan (2006). <a href="http://www.nowpublishers.com/article/Details/TCS-007">"Algorithmic Results in List Decoding"</a>. <i>Foundations and Trends® in Theoretical Computer Science</i>. 2 (2): 107–195. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1561%2F0400000007">10.1561/0400000007</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/1551-305X">1551-305X</a>.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://people.csail.mit.edu/madhu/FT01/">Notes from a course</a> taught by Madhu Sudan</li> <li><a href="http://www.cs.berkeley.edu/~luca/cs294/">Notes from a course</a> taught by <a href="/facts/Luca_Trevisan/oFlHonQ0">Luca Trevisan</a></li> <li><a href="http://www.cs.washington.edu/education/courses/533/06au/">Notes from a course</a> taught by <a href="/facts/Venkatesan_Guruswami/FLUy7glV">Venkatesan Guruswami</a></li> <li><a href="https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/">Notes from a course</a> taught by Atri Rudra</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Brakensiek, Joshua; Gopi, Sivakanth; Makam, Visu (2023-06-02). "Generic Reed-Solomon Codes Achieve List-Decoding Capacity". Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. New York, NY, USA: Association for Computing Machinery. pp. 1488–1501. arXiv:2206.05256. doi:10.1145/3564246.3585128. ISBN 978-1-4503-9913-5. <a href="978-1-4503-9913-5" target="_blank">978-1-4503-9913-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Guo, Zeyu; Zhang, Zihan (2023-11-06). "Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). FOCS 2023, Santa Cruz, CA, USA. IEEE. pp. 164–176. arXiv:2304.01403. doi:10.1109/FOCS57990.2023.00019. ISBN 979-8-3503-1894-4. <a href="979-8-3503-1894-4" target="_blank">979-8-3503-1894-4</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Alrabiah, Omar; Guruswami, Venkatesan; Li, Ray (2023). "Randomly punctured Reed--Solomon codes achieve list-decoding capacity over linear-sized fields". arXiv:2304.09445 [cs.IT]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>