Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
DOI10.4230/LIPICS.ITCS.2018.34zbMATH Open1462.68079arXiv1711.07960MaRDI QIDQ4993299FDOQ4993299
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
Recommendations
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)
Cites Work
- Powers of tensors and fast matrix multiplication
- Introduction to algorithms.
- Title not available (Why is that?)
- The buffer tree: A technique for designing batched external data structures
- Towards polynomial lower bounds for dynamic problems
- Cache-oblivious algorithms
- Multiplying matrices faster than coppersmith-winograd
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Matrix multiplication via arithmetic progressions
- Title not available (Why is that?)
- Algorithms and Data Structures
- Organization and maintenance of large ordered indexes
- Title not available (Why is that?)
- Systems of Logic Based on Ordinals†
- Title not available (Why is that?)
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Cache-oblivious dynamic programming
- I/O-efficient undirected shortest paths
- An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms
- Title not available (Why is that?)
- External-memory exact and approximate all-pairs shortest-paths in undirected graphs
- Title not available (Why is that?)
- Subcubic equivalences between graph centrality problems, APSP and diameter
- Automata, Languages and Programming
- Title not available (Why is that?)
- Algorithm Theory - SWAT 2004
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- The input/output complexity of sparse matrix multiplication
Cited In (7)
- Title not available (Why is that?)
- 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)
