Fetching the paper…
Reading the bibliography…
The $3$SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity.
Smoothing the gap between np and er
Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow · 1912
Earlier work this paper cites.
On sets of integers which contain no three terms in arithmetical progression
Felix A. Behrend · 1946
Earlier work this paper cites.
Algorithm 97: shortest path
Robert W. Floyd · 1962
Earlier work this paper cites.
Boolean matrix multiplication and transitive closure
Michael J. Fischer and Albert R. Meyer · 1971
Earlier work this paper cites.
String matching and other products
Michael J. Fischer and Michael S. Paterson · 1974
Earlier work this paper cites.
On the power of multiplication in random access machines
Juris Hartmanis and Janos Simon · 1974
Earlier work this paper cites.
New bounds on the complexity of the shortest path problem
Michael L. Fredman · 1976
Earlier work this paper cites.
An algorithm for finding all shortest paths using n 2.81 n^{2.81} infinite-precision multiplications
Gideon Yuval · 1976
Earlier work this paper cites.
On the power of random access machines
Arnold Schönhage · 1979
Earlier work this paper cites.
Lower bounds for algebraic computation trees
Michael Ben-Or · 1983
Earlier work this paper cites.
Arboricity and subgraph listing algorithms
Norishige Chiba and Takao Nishizeki · 1985
Earlier work this paper cites.
Generalized string matching
Karl Abrahamson · 1987
Earlier work this paper cites.
Witnesses for Boolean matrix multiplication and for shortest paths
Noga Alon, Zvi Galil, Oded Margalit, and Moni Naor · 1992
Earlier work this paper cites.
Lower bounds for linear satisfiability problems
Jeff Erickson · 1995
Earlier work this paper cites.
On a class of O ( n 2 ) {O}(n^{2}) problems in computational geometry
Anka Gajentaan and Mark H. Overmars · 1995
Earlier work this paper cites.
On the all-pairs-shortest-path problem in unweighted undirected graphs
R. Seidel · 1995
Earlier work this paper cites.
Finding and counting given length cycles
Noga Alon, Raphael Yuster, and Uri Zwick · 1997
Earlier work this paper cites.
Perfect binary space partitions
Mark de Berg, Marko M. de Groot, and Mark H. Overmars · 1997
Earlier work this paper cites.
Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard
Gill Barequet and Sariel Har-Peled · 1999
Earlier work this paper cites.
New lower bounds for convex hull problems in odd dimensions
Jeff Erickson · 1999
Earlier work this paper cites.
On the complexity of k k -SAT
Russell Impagliazzo and Ramamohan Paturi · 1999
Earlier work this paper cites.
On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
Simon Kahan and Jack Snoeyink · 1999
Earlier work this paper cites.
Smallest color-spanning objects
Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, Belén Palop, and Vera Sacristán · 2001
Earlier work this paper cites.
Preprocessing chains for fast dihedral rotations is hard or even impossible
Michael Soss, Jeff Erickson, and Mark Overmars · 2003
Earlier work this paper cites.
Finding a guard that sees most and a shop that sells most
Otfried Cheong, Alon Efrat, and Sariel Har-Peled · 2004
Earlier work this paper cites.
On dynamic shortest paths problems
Liam Roditty and Uri Zwick · 2004
Cited alongside, same era.
A new algorithm for optimal 2-constraint satisfaction and its implications
Ryan Williams · 2004
Cited alongside, same era.
Computing the set of all the distant horizons of a terrain
Daniel Archambault, William Evans, and David Kirkpatrick · 2005
Cited alongside, same era.
Subquadratic algorithms for 3SUM
Ilya Baran, Erik D. Demaine, and Mihai Patrascu · 2005
Cited alongside, same era.
Finding the smallest H -subgraph in real weighted graphs and related problems
Virginia Vassilevska, Ryan Williams, and Raphael Yuster · 2006
Cited alongside, same era.
On approximating the depth and related problems
Boris Aronov and Sariel Har-Peled · 2008
Cited alongside, same era.
On problems as hard as CNF-SAT
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström · 2016
Later among the works it cites.
Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider · 2016
Later among the works it cites.
Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky
Timothy M. Chan and R. Ryan Williams · 2016
Later among the works it cites.
On the hardness of partially dynamic graph problems and connections to diameter
Søren Dahlgaard · 2016
Later among the works it cites.
3 S U M \mathrm{3SUM} , 3 X O R \mathrm{3XOR} , triangles
Zahra Jafargholi and Emanuele Viola · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Computational Geometry: Algorithms and Applications
Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars · 2008
Cited alongside, same era.
The complexity of satisfiability of small depth circuits
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi · 2009
Cited alongside, same era.
Finding, minimizing, and counting weighted subgraphs
Virginia Vassilevska Williams and Ryan Williams · 2009
Cited alongside, same era.
On the exact complexity of evaluating quantified k k -CNF
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi · 2010
Cited alongside, same era.
On moderately exponential time for SAT
Evgeny Dantsin and Alexander Wolpert · 2010
Cited alongside, same era.
Towards polynomial lower bounds for dynamic problems
Mihai Pătraşcu · 2010
Cited alongside, same era.
Tsvi Kopelowitz, Seth Pettie, and Ely Porat · 2016
Later among the works it cites.
Deterministic time-space trade-offs for k k -SUM
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams · 2016
Later among the works it cites.
Improved subquadratic 3SUM
Ari Freund · 2017
Later among the works it cites.
Improved bounds for 3SUM, k k -SUM, and linear degeneracy
Omer Gold and Micha Sharir · 2017
Later among the works it cites.
Towards tight approximation bounds for graph diameter and eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein · 2018
Later among the works it cites.
More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
Timothy M. Chan · 2018
Later among the works it cites.
Fast hamiltonicity checking via bases of perfect matchings
Marek Cygan, Stefan Kratsch, and Jesper Nederlof · 2018
Later among the works it cites.
Towards unified approximate pattern matching for hamming and L 1 L_{1} distance
Paweł Gawrychowski and Przemysław Uznański · 2018
Later among the works it cites.
Near-optimal linear decision trees for k k -SUM and related problems
Daniel M. Kane, Shachar Lovett, and Shay Moran · 2018
Later among the works it cites.
Known algorithms on graphs of bounded treewidth are probably optimal
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh · 2018
Later among the works it cites.
Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
François Le Gall and Florent Urrutia · 2018
Later among the works it cites.
On some fine-grained questions in algorithms and complexity
Virginia Vassilevska Williams · 2018
Later among the works it cites.
Subquadratic algorithms for algebraic 3SUM
Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon · 2019
Later among the works it cites.
Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)
Karl Bringmann, Paweł Gawrychowski, Shay Mozes, and Oren Weimann · 2020
Later among the works it cites.
Reducing 3SUM to convolution-3SUM
Timothy M. Chan and Qizheng He · 2020
Later among the works it cites.
Equivalences between triangle and range query problems
Lech Duraj, Krzysztof Kleiner, Adam Polak, and Virginia Vassilevska Williams · 2020
Later among the works it cites.
Monochromatic triangles, intermediate matrix products, and convolutions
Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams · 2020
Later among the works it cites.
Monochromatic triangles, triangle listing and APSP
Virginia Vassilevska Williams and Yinzhan Xu · 2020
Later among the works it cites.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2021
Later among the works it cites.