Galactic algorithm: Difference between revisions

Revision as of 06:19, 5 October 2019

Latest revision as of 11:22, 29 July 2025

(163 intermediate revisions by 77 users not shown)

Line 1:

{{Short description|Classification of algorithm}}

A '''galactic algorithm''' is onean that[[algorithm]] runswith fasterrecord-breaking thantheoretical any([[Asymptotic othercomputational algorithmcomplexity|asymptotic]]) forperformance, problemsbut thatwhich is not used due to practical constraints. Typical reasons are sufficientlythat large,the butperformance wheregains "sufficientlyonly large"appear isfor problems that are so biglarge thatthey never occur, or the algorithm's iscomplexity neveroutweighs useda relatively small gain in practiceperformance. Galactic algorithms were so named by [[Richard Lipton]] and Ken Regan,<ref name="seminal">{{cite chapterbook |authorlast1=Lipton, |first1=Richard J., and|author-link1=Richard Lipton|first2=Kenneth W. |last2=Regan |chapter=David Johnson: Galactic Algorithms |title=People, Problems, and Proofs: Essays from Gödel's Lost Letter: 2010 |publisher=Springer Berlin |___location=Heidelberg |year=2013 |pages=109–112 |chapter-url=https://rjliptonbooks.wordpressgoogle.com/2010/10/23/galactic-algorithms/books?id=eLC9BAAAQBAJ&pg=PA109 |isbn=9783642414220}}</ref> asbecause they will never be used on any of the merely terrestrial data sets we find here on Earth.

== Possible use cases ==

An example of a galactic algorithm is the fastest known way to multiply two numbers,<ref>{{cite article|url=https://hal.archives-ouvertes.fr/hal-02070778 |title=Integer multiplication in time O(''n''&nbsp;log&nbsp;''n'') |author=David Harvey and Joris Van Der Hoeven|date=March 2019 }}</ref> which is based on a [[1729 (number)|1729]]-dimensional [[Fourier transform]].<ref>{{cite web |url=https://phys.org/news/2019-04-weve-quicker-big.html |title=We've found a quicker way to multiply really big numbers |author=David Harvey |date=Apr 10, 2019 |publisher=Phys.org}}</ref> This means it will not reach its stated efficiency until the numbers have at least 2¹⁷²⁹ digits, (vastly) more digits than there are atoms in the universe. So this algorithm is never used in practice.

DespiteEven the fact thatif they willare never beused usedin practice, galactic algorithms may still contribute to [[computer science]]:

* An algorithm, even if impractical, may show new techniques that may eventually be used to create practical algorithms. See, for example, communication channel capacity, below.

Despite the fact that they will never be used, galactic algorithms may still contribute to computer science:

* ComputerAvailable sizescomputational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical. See, for example, low-density parity-check codes, below.

* An algorithm, even if impractical, may show new techniques that may eventually be used to create practical algorithms.

* An impractical algorithm can still demonstrate that conjectured[[conjecture]]d bounds can be achieved, or alternatively show that conjecturedproposed bounds are wrong, and hence advance the theory of algorithms (see, for example, Reingold's algorithm for [[connectivity (graph theory)|connectivity]] in undirected graphs). As Lipton saysstates:<ref name="seminal"/>{{quote |This alone could be important and often is a great reason for finding such algorithms. For an example, if tomorrow there were tomorrow a discovery that showed there is a factoring algorithm with a huge but provably polynomial time bound, that would change our beliefs about factoring. The algorithm might never be used, but would certainly shape the future research into factoring."}} Similarly, a O(''N''^2¹⁰⁰)hypothetical algorithm for the [[Boolean satisfiability problem]] with a large but polynomial time bound, such as <math>\Theta\bigl(n^{2^{100}}\bigr)</math>, although unusable in practice, would settle the [[P versus NP problem]], considered the most important open problem in computer science and one of the [[Millennium Prize Problems]].<ref>{{cite journal |author=Fortnow, L. |year=2009 |title=The status of the P versus NP problem |journal=Communications of the ACM |volume=52 |issue=9 |pages=78-8678–86 |url=httphttps://peoplewww.cs.uchicagocmu.edu/~fortnow15326-f23/papers/pnpCACM-cacmFortnow.pdf|doi=10.1145/1562164.1562186 |s2cid=5969255 }}</ref><ref>{{cite journal One|author=Fortnow immediate|first=Lance practical|year=2022 effect|title=Fifty wouldYears beof toP earnVersus NP and the discovererPossibility [[Millenniumof Prizethe Impossible Problems|aurl=https://dl.acm.org/doi/pdf/10.1145/3460351 million|journal=Communications dollarof prize]]the fromACM the|volume=65 [[Clay|issue=1 Mathematics|pages=76–85 Institute]]|doi=10.1145/3460351 }}</ref>

* Computer sizes may catch up to the crossover point, so that a previously impractical algorithm becomes practical.

* An impractical algorithm can still demonstrate that conjectured bounds can be achieved, or alternatively show that conjectured bounds are wrong. As Lipton says "This alone could be important and often is a great reason for finding such algorithms. For an example, if there were tomorrow a discovery that showed there is a factoring algorithm with a huge but provably polynomial time bound that would change our beliefs about factoring. The algorithm might never be used, but would certainly shape the future research into factoring." Similarly, a O(''N''^2¹⁰⁰) algorithm for the [[Boolean satisfiability problem]], although unusable in practice, would settle the [[P versus NP problem]], the most important open problem in computer science.<ref>{{cite journal |author=Fortnow, L. |year=2009 |title=The status of the P versus NP problem |journal=Communications of the ACM |volume=52 |issue=9 |pages=78-86 |url=http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf}}</ref> One immediate practical effect would be to earn the discoverer [[Millennium Prize Problems|a million dollar prize]] from the [[Clay Mathematics Institute]].

== Examples ==

=== Integer multiplication ===

There are several well-known algorithms with world-beating asymptotic behavior, but only on impractically large problems:

An example of a galactic algorithm is the fastest known way to [[multiplication algorithm|multiply two numbers]],<ref>{{Cite journal|last1=David|first1=Harvey|last2=Hoeven|first2=Joris van der|date=March 2019|title=Integer multiplication in time O(n log n)|url=https://hal.archives-ouvertes.fr/hal-02070778/document|journal=HAL|volume=hal-02070778}}</ref> which is based on a 1729-dimensional [[Fourier transform]].<ref name="quick">{{cite web |last1=Harvey |first1=David |title=We've found a quicker way to multiply really big numbers |url=https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923 |website=The Conversation |date=9 April 2019 |access-date=9 March 2023 |language=en}}</ref> It needs <math>O(n \log n)</math> bit operations, but as the constants hidden by the [[big O notation]] are large, it is never used in practice. However, it also shows why galactic algorithms may still be useful. The authors state: "we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits."<ref name="quick"/>

*Matrix multiplication: The first improvement over brute-force multiplication, O(''N''³) is the [[Strassen algorithm]], a recursive algorithm that is O(''N''^2.807). This algorithm is not galactic and used in practice. Further extensions of this, using sophisticated group theory, are the [[Coppersmith–Winograd algorithm]] and its slightly better successors, delivering O(''N''^2.373). These are galactic – "We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical."<ref>{{citation

=== Primality testing ===

The [[AKS primality test]] is galactic. It is the most theoretically sound of any known algorithm that can take an arbitrary number and tell if it is [[prime number|prime]]. In particular, it is ''provably polynomial-time'', ''deterministic'', and ''unconditionally correct''. All other known algorithms fall short on at least one of these criteria, but the shortcomings are minor and the calculations are much faster, so they are used instead. [[Elliptic curve primality proving|ECPP]] in practice runs much faster than AKS, but it has never been proven to be polynomial time. The [[Miller–Rabin primality test|Miller–Rabin]] test is also much faster than AKS, but produces only a probabilistic result. However the probability of error can be driven down to arbitrarily small values (say <math>< 10^{-100}</math>), good enough for practical purposes. There is also a [[Miller–Rabin primality test#Deterministic variants|deterministic version]] of the Miller-Rabin test, which runs in polynomial time over all inputs, but its correctness depends on the [[generalized Riemann hypothesis]] (which is widely believed, but not proven). The existence of these (much) faster alternatives means AKS is not used in practice.

=== Matrix multiplication ===

*Matrix multiplication: The first improvement over brute-force [[matrix multiplication,]] O(''N''which needs <supmath>O(n^3)</supmath> multiplications) iswas the [[Strassen algorithm]],: a recursive algorithm that isneeds O(''N''<supmath>O(n^{2.807})</supmath>) multiplications. This algorithm is not galactic and is used in practice. Further extensions of this, using sophisticated [[group theory]], are the [[Coppersmith–Winograd algorithm]] and its slightly better successors, deliveringneeding O(''N''<supmath>O(n^{2.373})</supmath>). multiplications. These are galactic – "We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical."<ref>{{citation

| last = Le Gall | first = F.

| arxiv = 1204.1111

Line 17 ⟶ 23:

| pages = 514–523

| title = Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)

| year = 2012}}.</ref>| isbn = 978-0-7695-4874-6

| s2cid = 2410545

*[[Claude Shannon]] showed a simple but impractical code that could reach the capacity of a channel. It requires assigning a random code word to every possible N bit message, then decoding by finding the closest code word. If N is chosen large enough, this beats any existing code and can get arbitrarily close to the capacity of the channel. Unfortunately, any N big enough to beat existing codes is also completely impractical.<ref>{{cite web |url=https://news.mit.edu/2010/explained-shannon-0115 |title=Explained: The Shannon limit |publisher=MIT News Office |author=Larry Hardesty |date=Jan 19, 2010}}</ref> These codes, though never used, inspired decades of research into more practical algorithms that today can achieve rates arbitrarily close to channel capacity.

}}</ref>

*The problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a [[graph minor|minor]] is NP-complete in general, but where ''H'' is fixed, it can be solved in polynomial time. The running time for testing whether ''H'' is a minor of ''G'' in this case is ''O''(''n''²),<ref name="kkr12">{{cite journal |author=Kawarabayashi, K. I., Kobayashi, Y., & Reed, B. |year=2012 |title=The disjoint paths problem in quadratic time |journal=Journal of Combinatorial Theory, Series B |volume=102 |issue=2 |pages=424-435}}</ref> where ''n'' is the number of vertices in ''G'' and the [[big O notation]] hides a constant that depends superexponentially on ''H''. The constant is greater than <math> c > 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> (using [[Knuth's up-arrow notation]]), and where ''h'' is the number of vertices in ''H''.<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref>

*For cryptographers, a cryptographic "break" is anything faster than a brute-force attack – i.e., performing one trial decryption for each possible key in sequence. In many cases, even though they are the best known methods, they are still infeasible with current technology. One example is the best attack known against 128 bit AES, which takes only 2¹²⁶ operations.<ref name=":0">{{cite book |author=Biaoshuai Tao |title = Information Security and Privacy|volume = 9144|pages = 39–56|author2=Hongjun Wu |last-author-amp=yes |date=2015|doi=10.1007/978-3-319-19962-7_3 |series = Lecture Notes in Computer Science|isbn = 978-3-319-19961-0}}</ref> Despite being impractical, theoretical breaks can sometimes provide insight into vulnerability patterns.

=== Communication channel capacity ===

*[[Claude Shannon]] showed a simple but impracticalasymptotically optimal [[code]] that couldcan reach the theoretical capacity of a [[communication channel]]. It requires assigning a random code word to every possible N <math>n</math>-bit message, then decoding by finding the closest code word. If N<math>n</math> is chosen large enough, this beats any existing code and can get arbitrarily close to the capacity of the channel. Unfortunately, any N<math>n</math> big enough to beat existing codes is also completely impractical.<ref>{{cite web |url=https://news.mit.edu/2010/explained-shannon-0115 |title=Explained: The Shannon limit |publisher=MIT News Office |author=Larry Hardesty |date=JanJanuary 19, 2010}}</ref> These codes, though never used, inspired decades of research into more practical algorithms that today can achieve rates arbitrarily close to channel capacity.<ref>{{cite web |url=https://ocw.mit.edu/courses/6-451-principles-of-digital-communication-ii-spring-2005/1a3ad00d83d1d042da3328a8edd9edc2_chap13.pdf |title=Capacity-approaching codes (Chapter 13 of ''Principles Of Digital Communication II'') |publisher=[[MIT OpenCourseWare]] |date=2005}}</ref>

=== Sub-graphs ===

*The problem of [[decision problem|deciding]] whether a graph ''<math>G''</math> contains ''<math>H''</math> as a [[graph minor|minor]] is [[NP-complete]] in general, but where ''<math>H''</math> is fixed, it can be solved in polynomial time. The running time for testing whether ''<math>H''</math> is a minor of ''<math>G''</math> in this case is ''<math>O''(''n''<sup>^2)</supmath>),<ref name="kkr12">{{cite journal |authorlast1=Kawarabayashi, K.| I.,first1=Ken-ichi |last2=Kobayashi, Y.,| &first2=Yusuke |last3=Reed, B.| first3=Bruce | authorlink3=Bruce Reed (mathematician) |year=2012 |title=The disjoint paths problem in quadratic time |journal=[[Journal of Combinatorial Theory,]] | series=Series B |volume=102 |issue=2 |pages=424424–435|doi=10.1016/j.jctb.2011.07.004 |doi-435access=free }}</ref> where ''<math>n''</math> is the number of vertices in ''<math>G''</math> and the [[big O notation]] hides a constant that depends superexponentially on ''<math>H''</math>. The constant is greater than <math> c > 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> (usingin [[Knuth's up-arrow notation]]), and where ''<math>h''</math> is the number of vertices in ''<math>H''</math>.<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref> Even the case of <math>h = 4</math> cannot be reasonably computed as the constant is greater than 2 [[pentated]] by 4, or 2 [[tetrated]] by 65536, that is, <math>2 \uparrow \uparrow \uparrow 4 = {}^{65536}2 = \underbrace{2^{2^{\cdot^{\cdot^2}}}}_{65536}</math>.

=== Cryptographic breaks ===

*ForIn [[cryptography]] cryptographersjargon, a cryptographic "break" is anythingany attack faster thanin aexpectation brutethan [[Brute-force attack|brute force]] – i.e., performing one trial decryption for each possible key in sequence. InFor many casescryptographic systems, even though theybreaks are the best known methods, theybut are still practically infeasible with current technology. One example is the best attack known against 128 -bit [[Advanced Encryption Standard|AES]], which takes only 2<supmath>2^{126}</supmath> operations.<ref name=":0">{{cite book |author=Biaoshuai Tao |title = Information Security and Privacy|volume = 9144|pages = 39–56|author2=Hongjun Wu |lastname-authorlist-ampstyle=yesamp |date=2015|doi=10.1007/978-3-319-19962-7_3 |series = Lecture Notes in Computer Science|isbn = 978-3-319-19961-0}}</ref> Despite being impractical, theoretical breaks can sometimes provide insight into vulnerability patterns, and sometimes lead to discovery of exploitable breaks.

=== Traveling salesman problem ===

For several decades, the best known approximation to the [[traveling salesman problem]] in a [[metric space]] was the very simple [[Christofides algorithm]] which produced a path at most 50% longer than the optimum. (Many other algorithms could ''usually'' do much better, but could not provably do so.) In 2020, a newer and much more complex algorithm was discovered that can beat this by <math>10^{-34}</math> percent.<ref>{{cite arXiv |eprint=2007.01409 |class=cs.DS |title=A (Slightly) Improved Approximation Algorithm for Metric TSP |author1=Anna R. Karlin |author2=Nathan Klein |author3=Shayan Oveis Gharan |date=September 1, 2020}}</ref> Although no one will ever switch to this algorithm for its very slight worst-case improvement, it is still considered important because "this minuscule improvement breaks through both a theoretical logjam and a psychological one".<ref>{{cite web |author=Klarreich |first=Erica |date=8 October 2020 |title=Computer Scientists Break Traveling Salesperson Record |url=https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/ |website=Quanta Magazine}}</ref>

=== Hutter search ===

A single algorithm, "Hutter search", can solve any well-defined problem in an asymptotically optimal time, barring some caveats{{Such as|date=June 2025}}. It works by searching through all possible algorithms (by runtime), while simultaneously searching through all possible [[formal proof|proofs]] (by length of proof), looking for a proof of correctness for each algorithm. Since the proof of correctness is of finite size, it "only" adds a constant and does not affect the asymptotic runtime. However, this constant is so big that the algorithm is entirely impractical.<ref>{{cite arXiv|last=Hutter|first=Marcus|date=2002-06-14|title=The Fastest and Shortest Algorithm for All Well-Defined Problems|eprint=cs/0206022}}</ref><ref>{{Cite journal|last=Gagliolo|first=Matteo|date=2007-11-20|title=Universal search|journal=Scholarpedia|language=en|volume=2|issue=11|pages=2575|doi=10.4249/scholarpedia.2575|issn=1941-6016|bibcode=2007SchpJ...2.2575G|doi-access=free}}</ref> For example, if the shortest proof of correctness of a given algorithm is 1000 bits long, the search will examine at least 2⁹⁹⁹ other potential proofs first.

Hutter search is related to [[Solomonoff's theory of inductive inference|Solomonoff induction]], which is a formalization of [[Bayesian inference]]. All [[computable]] theories (as implemented by programs) which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. Again, the search over all possible explanations makes this procedure galactic.

=== Optimization ===

[[Simulated annealing]], when used with a logarithmic cooling schedule, has been proven to find the [[global optimum]] of any optimization problem. However, such a cooling schedule results in entirely impractical runtimes, and is never used.<ref>{{cite journal |last1=Liang |first1=Faming |first2=Yichen |last2=Cheng |first3=Guang |last3=Lin |title=Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule |journal=Journal of the American Statistical Association |volume=109 |issue=506 |year=2014 |pages=847–863|doi=10.1080/01621459.2013.872993 |s2cid=123410795 }}</ref> However, knowing this ideal algorithm exists has led to practical variants that are able to find very good (though not provably optimal) solutions to complex optimization problems.<ref>{{cite journal |author= Ingber, Lester |title=Simulated annealing: Practice versus theory |journal=Mathematical and Computer Modelling |volume=18 |issue=11 |year=1993 |pages=29–57|doi=10.1016/0895-7177(93)90204-C |doi-access=free |citeseerx=10.1.1.15.1046 }}</ref>

=== Minimum spanning trees ===

The [[expected linear time MST algorithm]] is able to discover the [[minimum spanning tree]] of a graph in <math>O(m + n)</math>, where <math>m</math> is the number of edges and <math>n</math> is the number of nodes of the graph.<ref>{{Cite journal |last1=Karger |first1=David R. |last2=Klein |first2=Philip N. |last3=Tarjan |first3=Robert E. |date=1995-03-01 |title=A randomized linear-time algorithm to find minimum spanning trees |journal=Journal of the ACM |volume=42 |issue=2 |pages=321–328 |doi=10.1145/201019.201022 |issn=0004-5411|doi-access=free }}</ref> However, the constant factor that is hidden by the [[Big O notation]] is huge enough to make the algorithm impractical. An implementation is publicly available<ref>{{Cite web |last=Thiesen |first=Francisco |title=A C++ implementation for an Expected Linear-Time Minimum Spanning Tree Algorithm(Karger-Klein-Tarjan + Hagerup Minimum Spanning Tree Verification as a sub-routine) |url=https://github.com/FranciscoThiesen/karger-klein-tarjan |access-date=2022-11-19 |website=[[GitHub]]}}</ref> and given the experimentally estimated implementation constants, it would only be faster than [[Borůvka's algorithm]] for graphs in which <math>m + n > 9 \cdot 10^{151}</math>.<ref>{{Cite web |last=Geiman Thiesen |first=Francisco |title=Expected Linear-Time Minimum Spanning Trees |url=https://franciscothiesen.github.io/Linear-Time-MST/ |access-date=2022-11-13 |website=franciscothiesen.github.io}}</ref>

=== Hash tables ===

Researchers have found an algorithm that achieves the provably best-possible<ref name="SuccinctDictionaries">{{cite conference | last1=Li | first1=Tianxiao | last2=Liang | first2=Jingxun | last3=Yu | first3=Huacheng | last4=Zhou | first4=Renfei | title=2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) | chapter=Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries | publisher=IEEE | date=6 November 2023 | page= | isbn=979-8-3503-1894-4 | doi=10.1109/FOCS57990.2023.00112 | doi-access=free | pages=1842–1862| arxiv=2306.02253 }}</ref> asymptotic performance in terms of time-space tradeoff.<ref>{{cite arXiv

| last1 = Bender

| first1 = Michael

| last2 = Farach-Colton

| first2 = Martin

| last3 = Kuszmaul

| first3 =John

| last4 = Kuszmaul

| first4 = William

| last5 = Mingmou

| first5 = Liu

| date = 4 Nov 2021

| title = On the Optimal Time/Space Tradeoff for Hash Tables

| eprint = 2111.00602

| class = cs

}}</ref> But it remains purely theoretical: "Despite the new hash table’s unprecedented efficiency, no one is likely to try building it anytime soon. It’s just too complicated to construct."<ref name="OptimalBalance">{{cite web | last=Nadis | first=Steve | title=Scientists Find Optimal Balance of Data Storage and Time | website=Quanta Magazine | date=8 February 2024 | url=https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/ | access-date=12 February 2025}}</ref> and "in practice, constants really matter. In the real world, a factor of 10 is a game ender.”<ref name="OptimalBalance"/>

=== Connectivity in undirected graphs ===

Connectivity in undirected graphs (also known as USTCON, for Unconnected Source-Target CONnectivity) is the problem of deciding if a path exists between two nodes in an undirected graph, or in other words, if they are in the same [[Component (graph theory)|connected component]]. When the usage of <math>O(\text{N})</math> space is allowed, polynomial time solutions such as [[Dijkstra's algorithm]] have been known and used for decades. But for many years it was unknown if this could be done deterministically in <math>O(\text{log N})</math> space (class '''[[L (complexity)|L]]'''), though it was known to be possible with randomized algorithms (class '''RL''').

A breakthrough 2004 paper by [[Omer Reingold]] showed that USTCON is in fact in '''[[L (complexity)|L]]''',<ref>{{citation

| last = Reingold | first = Omer | author-link = Omer Reingold

| doi = 10.1145/1391289.1391291

| issue = 4

| journal = [[Journal of the ACM]]

| mr = 2445014

| pages = 1–24

| title = Undirected connectivity in log-space

| volume = 55

| year = 2008}}.</ref> providing an algorithm with asymptotically better space requirement. However, [[SL (complexity)#Omer Reingold, 2004|the algorithm's very big constant]] hidden by the <math>O(\text{log N})</math> means that on any realistic problem it consumes significantly more memory and computation time than the well known <math>O(\text{N})</math> algorithms. Despite not being used in practice, the paper is still a landmark in theory, and has been cited more than 1000 times as of 2025.

=== Low-density parity-check codes ===

'''[[Low-density parity-check code]]s''', also known as '''LDPC''' or '''Gallager''' codes, are an example of an algorithm that was galactic when first developed, but became practical as computation improved. They were originally conceived by [[Robert G. Gallager]] in his doctoral dissertation<ref>{{cite thesis |last=Gallager |first=Robert G. |date= 1960 |title=Low density parity check codes |url=https://dspace.mit.edu/bitstream/handle/1721.1/11804/32786367-MIT.pdf |degree=Ph.D |publisher=Massachusetts Institute of Technology }}</ref> at the [[Massachusetts Institute of Technology]] in 1960.<ref>{{Cite news |last=Hardesty |first=L. |date=January 21, 2010 |title=Explained: Gallager codes |url=http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html |access-date=August 7, 2013 |journal=MIT News}}</ref><ref name="G1962">{{cite journal |last=Gallager |first=R.G. |date=January 1962 |title=Low density parity check codes |journal=IRE Trans. Inf. Theory |volume=8 |issue=1 |pages=21–28 |doi=10.1109/TIT.1962.1057683 |s2cid=260490814 |hdl=1721.1/11804/32786367-MIT}}</ref> Although their performance was much better than other codes of that time, reaching the [[Gilbert–Varshamov bound for linear codes]], the codes were largely ignored as their iterative decoding algorithm was prohibitively computationally expensive for the hardware available.<ref>{{cite journal |title=The development of turbo and LDPC codes for deep-space applications |last1=Andrews |first1=Kenneth S |last2=Divsalar |first2=Dariush |last3=Dolinar |first3=Sam |last4=Hamkins |first4=Jon |last5=Jones |first5=Christopher R |last6=Pollara |first6=Fabrizio |journal=Proceedings of the IEEE |volume=95 |number=11 |pages=2142–2156 |year=2007 |publisher=IEEE |doi=10.1109/JPROC.2007.905132 |url=http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf |archive-date=2009-06-20 |access-date=2025-03-04 |archive-url=https://web.archive.org/web/20090620174506/http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf |url-status=bot: unknown }}</ref>

Renewed interest in LDPC codes emerged following the invention of the closely related [[turbo code]]s (1993), whose similarly iterative decoding algorithm outperformed other codes used at that time. LDPC codes were subsequently rediscovered in 1996,<ref name="MacKay96">{{cite journal

|title=Near Shannon limit performance of low density parity check codes

|last1=MacKay |first1=David JC |author1-link=David J. C. MacKay|last2=Neal |first2=Radford M |author2-link=Radford M. Neal

|journal=Electronics Letters

|volume=32

|number=18

|pages=1645–1646

|year=1996

|publisher=IET

|doi=10.1049/el:19961141 |bibcode=1996ElL....32.1645M |url=https://docs.switzernet.com/people/emin-gabrielyan/060708-thesis-ref/papers/MacKay96.pdf}}</ref> and became popular as a patent-free alternative.<ref name="Closing">{{cite journal |author=Erico Guizzo |date=Mar 1, 2004 |title=CLOSING IN ON THE PERFECT CODE |url=https://spectrum.ieee.org/closing-in-on-the-perfect-code |url-status=dead |journal=IEEE Spectrum |archive-url=https://web.archive.org/web/20210902170851/https://spectrum.ieee.org/closing-in-on-the-perfect-code |archive-date=September 2, 2021}} "Another advantage, perhaps the biggest of all, is that the LDPC patents have expired, so companies can use them without having to pay for intellectual-property rights."</ref> Even though the turbo code patents have now expired, LDPC codes also have some technical advantages, and are used in many applications today.

== References ==