Fetching the paper…
Reading the bibliography…
This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity (conditional polynomial lower bounds).
Systems of logic based on ordinals
A. M. Turing · 1939
Earlier work this paper cites.
Organization and maintenance of large ordered indices
R. Bayer and E. McCreight · 1970
Earlier work this paper cites.
Time-bounded random access machines
Stephen A. Cook and Robert A. Reckhow · 1972
Earlier work this paper cites.
Relations among complexity measures
Nicholas Pippenger and Michael J Fischer · 1979
Earlier work this paper cites.
I/O complexity: The red-blue pebble game
Jia-Wei Hong and H. T. Kung · 1981
Earlier work this paper cites.
I/o complexity: The red-blue pebble game
Hong Jia-Wei and Hsiang-Tsung Kung · 1981
Earlier work this paper cites.
The input/output complexity of sorting and related problems
Alok Aggarwal and S. Vitter, Jeffrey · 1988
Earlier work this paper cites.
Matrix multiplication via arithmetic progressions
Don Coppersmith and Shmuel Winograd · 1990
Earlier work this paper cites.
On the all-pairs-shortest-path problem
Raimund Seidel · 1992
Earlier work this paper cites.
External-memory graph algorithms
Yi-Jen Chiang, Michael T Goodrich, Edward F Grove, Roberto Tamassia, Darren Erik Vengroff, and Jeffrey Scott Vitter · 1995
Earlier work this paper cites.
External-memory algorithms with applications in gis
Lars Arge · 1997
Earlier work this paper cites.
Cache-oblivious algorithms
Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran · 1999
Earlier work this paper cites.
Recursively enumerable sets and degrees: A study of computable functions and computably generated sets
Robert I. Soare · 1999
Earlier work this paper cites.
External memory algorithms and data structures: dealing with massive data
Jeffrey Scott Vitter · 2001
Earlier work this paper cites.
A probabilistic-time hierarchy theorem for “slightly non-uniform” algorithms
Boaz Barak · 2002
Earlier work this paper cites.
Two simplified algorithms for maintaining order in a list
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito · 2002
Earlier work this paper cites.
Cache-oblivious algorithms and data structures
Erik D. Demaine · 2002
Cited alongside, same era.
External-memory breadth-first search with sublinear i/o
Kurt Mehlhorn and Ulrich Meyer · 2002
Cited alongside, same era.
The buffer tree: A technique for designing batched external data structures
Lars Arge · 2003
Cited alongside, same era.
I/o-efficient undirected shortest paths
Ulrich Meyer and Norbert Zeh · 2003
Cited alongside, same era.
External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs
Lars Arge, Ulrich Meyer, and Laura Toma · 2004
Cited alongside, same era.
Cache-oblivious algorithms and data structures
Gerth Stølting Brodal · 2004
Cited alongside, same era.
Towards polynomial lower bounds for dynamic problems
Mihai Pǎtraşcu · 2010
Later among the works it cites.
Subcubic equivalences between path, matrix and triangle problems
Virginia Vassilevska Williams and Ryan Williams · 2010
Later among the works it cites.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Later among the works it cites.
Fast approximation algorithms for the diameter and radius of sparse graphs
Liam Roditty and Virginia Vassilevska Williams · 2013
Later among the works it cites.
Finding, minimizing, and counting weighted subgraphs
Virginia Vassilevska Williams and Ryan Williams · 2013
Later among the works it cites.
Popular conjectures imply strong lower bounds for dynamic problems
Amir Abboud and Virginia Vassilevska Williams · 2014
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cache-oblivious shortest paths in graphs using buffer heap
Rezaul Alam Chowdhury and Vijaya Ramachandran · 2004
Cited alongside, same era.
Subquadratic algorithms for 3sum
Ilya Baran, Erik D Demaine, and Mihai Pǎtraşcu · 2005
Cited alongside, same era.
External-memory exact and approximate all-pairs shortest-paths in undirected graphs
Rezaul Alam Chowdhury and Vijaya Ramachandran · 2005
Cited alongside, same era.
Cache-oblivious dynamic programming
Rezaul Alam Chowdhury and Vijaya Ramachandran · 2006
Cited alongside, same era.
Cache-oblivious dynamic programming
Rezaul Alam Chowdhury and Vijaya Ramachandran · 2006
Cited alongside, same era.
Algorithm engineering for large data sets
Roman Dementiev · 2006
Cited alongside, same era.
Later among the works it cites.
Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
Karl Bringmann · 2014
Later among the works it cites.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Later among the works it cites.
The input/output complexity of triangle enumeration
Rasmus Pagh and Francesco Silvestri · 2014
Later among the works it cites.
The input/output complexity of sparse matrix multiplication
Rasmus Pagh and Morten Stöckel · 2014
Later among the works it cites.
If the current clique algorithms are optimal, so is Valiant’s parser
Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams · 2015
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.
Subcubic equivalences between graph centrality problems, APSP and diameter
Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams · 2015
Later among the works it cites.
Edit distance cannot be computed in strongly subquadratic time (unless seth is false)
Arturs Backurs and Piotr Indyk · 2015
Later among the works it cites.
Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs
Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang · 2016
Later among the works it cites.