Editing Subset sum problem (section)

=== Howgrave-Graham and Joux ===
In 2010, Howgrave-Graham and Joux<ref>{{Cite book|last1=Howgrave-Graham|first1=Nick|last2=Joux|first2=Antoine|title=Advances in Cryptology – EUROCRYPT 2010 |chapter=New Generic Algorithms for Hard Knapsacks |date=2010|editor-last=Gilbert|editor-first=Henri|series=Lecture Notes in Computer Science|volume=6110|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=235–256|doi=10.1007/978-3-642-13190-5_12|isbn=978-3-642-13190-5|doi-access=free}}</ref> presented a [[probabilistic algorithm]] that runs faster than all previous ones - in time <math>O(2^{0.337n})</math> using space <math>O(2^{0.256n})</math>. It solves only the decision problem, cannot prove there is no solution for a given sum, and does not return the subset sum closest to ''T''.

The techniques of Howgrave-Graham and Joux were subsequently extended<ref>{{Cite book|last1=Becker|first1=Anja|last2=Coron|first2=Jean-Sébastien|last3=Joux|first3=Antoine|title=Advances in Cryptology – EUROCRYPT 2011 |chapter=Improved Generic Algorithms for Hard Knapsacks |date=2011|editor-last=Patterson|editor-first=Kenneth|series=Lecture Notes in Computer Science|volume=6632|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=364–385|doi=10.1007/978-3-642-20465-4_21|isbn=978-3-642-20465-4|doi-access=free}}</ref> bringing the time complexity to <math>O(2^{0.291n})</math>. A more recent generalization<ref>{{Cite book|last1=Bonnetain|first1=Xavier|last2=Bricout|first2=Rémi|last3=Schrottenloher|first3=André|last4=Shen|first4=Yixin|title=Advances in Cryptology - ASIACRYPT 2020 |chapter=Improved Classical and Quantum Algorithms for Subset-Sum |date=2020|editor-last1=Moriai|editor-first1=Shiho|editor-last2=Wang|editor-first2=Huaxiong|series=Lecture Notes in Computer Science|volume=12492|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=633-666|doi=10.1007/978-3-030-64834-3_22|isbn=978-3-030-64833-6|doi-access=free}}</ref> lowered the time complexity to <math>O(2^{0.283n})</math>.