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

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

© Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams. This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity (conditional polynomial lower bounds). Specifically, we aim to answer why sp...

Full description

Bibliographic Details
Main Authors: Williams, Virginia Vassilevska, Demaine, Erik, Lincoln, Andrea, Liu, Quanquan C., Lynch, Jayson
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: 2021
Online Access:https://hdl.handle.net/1721.1/137672

Similar Items

Similar Items