Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy

DOI10.4230/LIPICS.ITCS.2018.34MaRDI QIDQ4993299zbMATH OpenFDO

Authors Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Williams Virginia Vassilevska

Publication date 15 June 2021

Full work available at URL https://arxiv.org/abs/1711.07960

zbMATH Keywords

algorithmsfine-grained complexityIO model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• scientific article; zbMATH DE number 1305462
• I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
• Automata, Languages and Programming
• Fine-grained complexity for sparse graphs
• I/O-efficient undirected shortest paths

Cites work

• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3557235 (Why is no real title available?)
• scientific article; zbMATH DE number 1947389 (Why is no real title available?)
• scientific article; zbMATH DE number 1947435 (Why is no real title available?)
• scientific article; zbMATH DE number 2019635 (Why is no real title available?)
• scientific article; zbMATH DE number 910869 (Why is no real title available?)
• Algorithm Theory - SWAT 2004
• Algorithms and Data Structures
• An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Automata, Languages and Programming
• Cache-oblivious algorithms
• Cache-oblivious dynamic programming
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• External-memory exact and approximate all-pairs shortest-paths in undirected graphs
• Fast approximation algorithms for the diameter and radius of sparse graphs
• I/O-efficient undirected shortest paths
• Introduction to algorithms.
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• Organization and maintenance of large ordered indexes
• Powers of tensors and fast matrix multiplication
• Subcubic equivalences between graph centrality problems, APSP and diameter
• Systems of Logic Based on Ordinals^†
• The buffer tree: A technique for designing batched external data structures
• The input/output complexity of sparse matrix multiplication
• Towards polynomial lower bounds for dynamic problems

Cited in

(7)

• scientific article; zbMATH DE number 1515868 (Why is no real title available?)
• Scheduling lower bounds via AND subset sum
• The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
• Computing the optimal IO sequences of a protocol in polynomial time
• Upper and lower I/O bounds for pebbling \(r\)-pyramids
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Fine-Grained Complexity Theory (Tutorial)

This page was built for publication: Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993299)