Fetching the paper…
Reading the bibliography…
A noticeable fraction of Algorithms papers in the last few decades improve the running time of well-known algorithms for fundamental problems by logarithmic factors.
Realizations of linear functions by formulas using+
B. A. Subbotovskaya · 1961
Earlier work this paper cites.
Programming techniques: Regular expression search algorithm
K. Thompson · 1968
Earlier work this paper cites.
On economic construction of the transitive closure of a direct graph
V. Arlazarov, E. Dinic, I. Faradzev, and M. Kronrod · 1970
Earlier work this paper cites.
Method of determining lower bounds for the complexity of p-schemes
V. M. Khrapchenko · 1971
Earlier work this paper cites.
On time-hardware complexity tradeoffs for boolean functions
P. M. Spira · 1971
Earlier work this paper cites.
The string-to-string correction problem
R. A. Wagner and M. J. Fischer · 1974
Earlier work this paper cites.
On time versus space
J. Hopcroft, W. Paul, and L. Valiant · 1977
Earlier work this paper cites.
A faster algorithm computing string edit distances
W. J. Masek and M. S. Paterson · 1980
Earlier work this paper cites.
Identification of common molecular subsequences
T. F. Smith and M. S. Waterman · 1981
Earlier work this paper cites.
A bit-string longest-common-subsequence algorithm
L. Allison and T. I. Dix · 1986
Earlier work this paper cites.
About one method of obtaining more than quadratic effective lower bounds of complexity of pi-schemes, 1987
A. E. Andreev · 1987
Earlier work this paper cites.
A natural metric for curves - computing the distance for polygonal chains and approximation algorithms
M. Godau · 1991
Earlier work this paper cites.
A four russians algorithm for regular expression pattern matching
G. Myers · 1992
Earlier work this paper cites.
The effect of random restrictions on formula size
R. Impagliazzo and N. Nisan · 1993
Earlier work this paper cites.
Shrinkage of de morgan formulae under restriction
M. S. Paterson and U. Zwick · 1993
Earlier work this paper cites.
Size-depth tradeoffs for boolean fomulae
M. L. Bonet and S. R. Buss · 1994
Earlier work this paper cites.
Computing discrete Fréchet distance
T. Eiter and H. Mannila · 1994
Earlier work this paper cites.
Computing the Fréchet distance between two polygonal curves
H. Alt and M. Godau · 1995
Earlier work this paper cites.
Gapped blast and psi-blast: a new generation of protein database search programs
S. F. Altschul, T. L. Madden, A. A. Schäffer, J. Zhang, Z. Zhang, W. Miller, and D. J. Lipman · 1997
Earlier work this paper cites.
The shrinkage exponent of de morgan formulas is 2
J. Håstad · 1998
Earlier work this paper cites.
Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification
M. E. Munich and P. Perona · 1999
Earlier work this paper cites.
Introduction to algorithms
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein · 2001
Earlier work this paper cites.
A fast and practical bit-vector algorithm for the longest common subsequence problem
M. Crochemore, C. S. Iliopoulos, Y. J. Pinzon, and J. F. Reid · 2001
Earlier work this paper cites.
On the complexity of k-sat
R. Impagliazzo and R. Paturi · 2001
Earlier work this paper cites.
Approximate nearest neighbor algorithms for Fréchet distance via product metrics
P. Indyk · 2002
Earlier work this paper cites.
A subquadratic sequence alignment algorithm for unrestricted scoring matrices
M. Crochemore, G. M. Landau, and M. Ziv-Ukelson · 2003
Earlier work this paper cites.
Comparison of distance measures for planar curves
H. Alt, C. Knauer, and C. Wenk · 2004
Earlier work this paper cites.
Bit-parallel lcs-length computation revisited
H. Hyyrö · 2004
Earlier work this paper cites.
On map-matching vehicle tracking data
S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk · 2005
Earlier work this paper cites.
An improved exponential-time algorithm for k -sat
R. Paturi, P. Pudlák, M. E. Saks, and F. Zane · 2005
Earlier work this paper cites.
A new algorithm for optimal 2-constraint satisfaction and its implications
R. Williams · 2005
Earlier work this paper cites.
Fréchet distance for curves, revisited
B. Aronov, S. Har-Peled, C. Knauer, Y. Wang, and C. Wenk · 2006
Earlier work this paper cites.
A duality between clause width and clause density for SAT
C. Calabro, R. Impagliazzo, and R. Paturi · 2006
Earlier work this paper cites.
160-fold acceleration of the smith-waterman algorithm using a field programmable gate array (fpga)
I. T. Li, W. Shum, and K. Truong · 2007
Earlier work this paper cites.
Subquadratic algorithms for 3sum
I. Baran, E. D. Demaine, and M. Patrascu · 2008
Cited alongside, same era.
Fast and compact regular expression matching
P. Bille and M. Farach-Colton · 2008
Cited alongside, same era.
Regularity lemmas and combinatorial algorithms
N. Bansal and R. Williams · 2009
Cited alongside, same era.
Faster regular expression matching
P. Bille and M. Thorup · 2009
Cited alongside, same era.
Exact algorithms for partial curve matching via the Fréchet distance
K. Buchin, M. Buchin, and Y. Wang · 2009
Cited alongside, same era.
The complexity of satisfiability of small depth circuits
C. Calabro, R. Impagliazzo, and R. Paturi · 2009
Cited alongside, same era.
Worst-case upper bounds
An improved deterministic# sat algorithm for small de morgan formulas
R. Chen, V. Kabanets, and N. Saurabh · 2014
Later among the works it cites.
New tabulation and sparse dynamic programming based techniques for sequence similarity problems
S. Grabowski · 2014
Later among the works it cites.
Threesomes, degenerates, and love triangles
A. Grønlund and S. Pettie · 2014
Later among the works it cites.
0-1 integer linear programming with a linear number of constraints
R. Impagliazzo, S. Lovett, R. Paturi, and S. Schneider · 2014
Later among the works it cites.
Shrinkage of de morgan formulae by spectral techniques
A. Tal · 2014
Later among the works it cites.
Algorithms for Circuits and Circuits for Algorithms: Connecting the Tractable and Intractable
R. Williams · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
E. Dantsin and E. A. Hirsch · 2009
Cited alongside, same era.
Can we compute the similarity between surfaces?
H. Alt and M. Buchin · 2010
Cited alongside, same era.
Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
E. W. Chambers, É. Colin de Verdière, J. Erickson, S. Lazard, F. Lazarus, and S. Thite · 2010
Cited alongside, same era.
Geodesic Fréchet distance inside a simple polygon
A. F. Cook and C. Wenk · 2010
Cited alongside, same era.
On the possibility of faster SAT algorithms
M. Patrascu and R. Williams · 2010
Cited alongside, same era.
Fighting perebor: New and improved algorithms for formula and QBF satisfiability
R. Santhanam · 2010
Cited alongside, same era.
Faster all-pairs shortest paths via circuit complexity
R. Williams · 2014
Later among the works it cites.
New algorithms and lower bounds for circuits with linear threshold gates
R. Williams · 2014
Later among the works it cites.
Nonuniform ACC circuit lower bounds
R. Williams · 2014
Later among the works it cites.
Tight Hardness Results for LCS and other Sequence Similarity Measures
A. Abboud, A. Backurs, and V. Vassilevska Williams · 2015
Later among the works it cites.
Matching triangles and basing hardness on an extremely popular conjecture
A. Abboud, V. Vassilevska Williams, and H. Yu · 2015
Later among the works it cites.
More applications of the polynomial method to algorithm design
A. Abboud, R. Williams, and H. Yu · 2015
Later among the works it cites.
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
A. Backurs and P. Indyk · 2015
Later among the works it cites.
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
K. Bringmann and M. Künnemann · 2015
Later among the works it cites.
Speeding up the four russians algorithm by about one more logarithmic factor
T. M. Chan · 2015
Later among the works it cites.
Satisfiability algorithms and lower bounds for boolean formulas over finite bases
R. Chen · 2015
Later among the works it cites.
Correlation bounds and #sat algorithms for small linear-size circuits
R. Chen and V. Kabanets · 2015
Later among the works it cites.
Mining circuit lower bound proofs for meta-algorithms
R. Chen, V. Kabanets, A. Kolokolova, R. Shaltiel, and D. Zuckerman · 2015
Later among the works it cites.
A satisfiability algorithm for depth-2 circuits with a symmetric gate at the top and and gates at the bottom
T. Sakai, K. Seto, S. Tamaki, and J. Teruyama · 2015
Later among the works it cites.
#sat algorithms from shrinkage
A. Tal · 2015
Later among the works it cites.
An improved combinatorial algorithm for boolean matrix multiplication
H. Yu · 2015
Later among the works it cites.
Subtree isomorphism revisited
A. Abboud, A. Backurs, T. D. Hansen, V. Vassilevska Williams, and O. Zamir · 2016
Later among the works it cites.
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
A. Abboud, T. D. Hansen, V. V. Williams, and R. Williams · 2016
Later among the works it cites.
Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs
A. Abboud, V. Vassilevska Williams, and J. R. Wang · 2016
Later among the works it cites.
Which regular expression patterns are hard to match?
A. Backurs and P. Indyk · 2016
Later among the works it cites.
A dichotomy for regular expression membership testing
K. Bringmann, A. Grønlund, and K. G. Larsen · 2016
Later among the works it cites.
New bounds for approximating extremal distances in undirected graphs
M. Cairo, R. Grossi, and R. Rizzi · 2016
Later among the works it cites.
Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction
K. Chatterjee, W. Dvorák, M. Henzinger, and V. Loitzenbauer · 2016
Later among the works it cites.
Satisfiability on mixed instances
R. Chen and R. Santhanam · 2016
Later among the works it cites.
Circuit size lower bounds and# sat upper bounds through a general framework
A. Golovnev, A. S. Kulikov, A. Smal, and S. Tamaki · 2016
Later among the works it cites.
Subquadratic algorithms for succinct stable matching
D. Moeller, R. Paturi, and S. Schneider · 2016
Later among the works it cites.
Improved subquadratic 3sum
A. Freund · 2017
Later among the works it cites.
Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
O. Gold and M. Sharir · 2017
Later among the works it cites.
More logarithmic-factor speedups for 3sum, (median,+)-convolution, and some geometric 3sum-hard problems
T. M. Chan · 2018
Closest in time.