Fetching the paper…
Reading the bibliography…
The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size $n$ into smaller subproblems (say, $a$ copies of size $n/b$ each), along with some auxiliary work of cost $C^{\textrm{aux}}(n)$, to give a recurrence relation $$C(n) \leq a \, C(n/b) + C^{\textrm{aux}}(n)$$ for the classical complexity $C(n)$.
Quicksort
C. A. R. Hoare · 1962
Earlier work this paper cites.
Multiplication of multidigit numbers on automata
Anatolij A. Karatsuba and Yu. Ofman · 1963
Earlier work this paper cites.
An algorithm for the machine calculation of complex Fourier series
James W. Cooley and John W. Tukey · 1965
Earlier work this paper cites.
Gaussian elimination is not optimal
Volker Strassen · 1969
Earlier work this paper cites.
The string-to-string correction problem
Robert A. Wagner and Michael J. Fischer · 1974
Earlier work this paper cites.
On computing the length of longest increasing subsequences
Michael L. Fredman · 1975
Earlier work this paper cites.
A general method for solving divide-and-conquer recurrences
Jon Louis Bentley, Dorothea Haken, and James B. Saxe · 1980
Earlier work this paper cites.
Matrix multiplication via arithmetic progressions
Don Coppersmith and Shmuel Winograd · 1990
Earlier work this paper cites.
Computing with noisy information
Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal · 1994
Earlier work this paper cites.
A quantum algorithm for finding the minimum, 1996
Christoph Dürr and Peter Høyer · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Incremental string comparison
Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt · 1998
Earlier work this paper cites.
Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem
David Aldous and Persi Diaconis · 1999
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001
Earlier work this paper cites.
Quantum amplitude amplification and estimation
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp · 2002
Earlier work this paper cites.
String matching in O ~ ( n + m ) \tilde{O}(\sqrt{n}+\sqrt{m}) quantum time
H. Ramesh and V. Vinay · 2003
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
Scott Aaronson and Yaoyun Shi · 2004
Cited alongside, same era.
Quantum lower and upper bounds for 2 D 2D -grid and Dyck language
Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs · 2007
Cited alongside, same era.
Quantum walk algorithm for element distinctness
Andris Ambainis · 2007
Cited alongside, same era.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert Špalek · 2007
Cited alongside, same era.
Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein · 2009
Cited alongside, same era.
Span-program-based quantum algorithm for evaluating unbalanced formulas, 2009
Span-program-based quantum algorithm for evaluating formulas
Ben Reichardt and Robert Špalek · 2012
Later among the works it cites.
Quantum adversary (upper) bound
Shelby Kimmel · 2013
Later among the works it cites.
Quantum algorithms for learning symmetric juntas via adversary bound
Aleksandrs Belovs · 2014
Later among the works it cites.
Tight hardness results for LCS and other sequence similarity measures
Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams · 2015
Later among the works it cites.
Improved quantum query algorithms for triangle detection and associativity testing
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Ben W. Reichardt · 2009
Cited alongside, same era.
Ben W. Reichardt · 2009
Cited alongside, same era.
Polylogarithmic approximation for edit distance and the asymmetric query complexity
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak · 2010
Cited alongside, same era.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2010
Cited alongside, same era.
An adversary for algorithms, 2010
Troy Lee, Rajat Mittal, Ben W. Reichardt, and Robert Špalek · 2010
Cited alongside, same era.
Estimating the longest increasing sequence in polylogarithmic time
Michael Saks and C. Seshadhri · 2010
Cited alongside, same era.
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy · 2011
Cited alongside, same era.
Troy Lee, Frédéric Magniez, and Miklos Santha · 2017
Later among the works it cites.
Fine-grained reductions and quantum speedups for dynamic programming
Amir Abboud · 2019
Later among the works it cites.
Quantum speedups for exponential-time dynamic programming algorithms
Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, and Jevgēnijs Vihrovs · 2019
Later among the works it cites.
A quantum query complexity trichotomy for regular languages
Scott Aaronson, Daniel Grier, and Luke Schaeffer · 2019
Later among the works it cites.
Approximation algorithms for LCS and LIS with truly improved running times
Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun · 2019
Later among the works it cites.
Span programs and quantum time complexity
Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita · 2020
Later among the works it cites.
Improved approximation for longest common subsequence over small alphabets
Shyan Akmal and Virginia Vassilevska Williams · 2021
Later among the works it cites.
Quantum speedups for dynamic programming on n n -dimensional lattice graphs
Adam Glos, Martins Kokainis, Ryuhei Mori, and Jevgēnijs Vihrovs · 2021
Later among the works it cites.
Near-optimal quantum algorithms for string problems
Shyan Akmal and Ce Jin · 2022
Closest in time.
Span programs and quantum space complexity
Stacey Jeffery · 2022
Closest in time.
Quantum speedups for treewidth
Vladislavs Kļevickis, Krišjānis Prūsis, and Jevgēnijs Vihrovs · 2022
Closest in time.