License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.34
URN: urn:nbn:de:0030-drops-83335
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8333/
Demaine, Erik D. ;
Lincoln, Andrea ;
Liu, Quanquan C. ;
Lynch, Jayson ;
Vassilevska Williams, Virginia
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy
Abstract
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 sparse graph problems are so hard, and why the Longest Common Subsequence problem gets a savings of a factor of the size of cache times the length of a cache line, but no more. We take the reductions and techniques from complexity and fine-grained complexity and apply them to the I/O model to generate new (conditional) lower bounds as well as new faster algorithms. We also prove the existence of a time hierarchy for the I/O model, which motivates the fine-grained reductions.
- Using fine-grained reductions, we give an algorithm for distinguishing 2 vs. 3 diameter and radius that runs in O(|E|^2/(MB)) cache misses, which for sparse graphs improves over the previous O(|V|^2/B) running time.
- We give new reductions from radius and diameter to Wiener index and median. These reductions are new in both the RAM and I/O models.
- We show meaningful reductions between problems that have linear-time solutions in the RAM model. The reductions use low I/O complexity (typically O(n/B)), and thus help to finely capture between "I/O linear time" O(n/B) and RAM linear time O(n).
- We generate new I/O assumptions based on the difficulty of improving sparse graph problem running times in the I/O model. We create conjectures that the current best known algorithms for Single Source Shortest Paths (SSSP), diameter, and radius are optimal.
- From these I/O-model assumptions, we show that many of the known reductions in the word-RAM model can naturally extend to hold in the I/O model as well (e.g., a lower bound on the I/O complexity of Longest Common Subsequence that matches the best known running time).
- We prove an analog of the Time Hierarchy Theorem in the I/O model, further motivating the study of fine-grained algorithmic differences.
BibTeX - Entry
@InProceedings{demaine_et_al:LIPIcs:2018:8333,
author = {Erik D. Demaine and Andrea Lincoln and Quanquan C. Liu and Jayson Lynch and Virginia Vassilevska Williams},
title = {{Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {34:1--34:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8333},
URN = {urn:nbn:de:0030-drops-83335},
doi = {10.4230/LIPIcs.ITCS.2018.34},
annote = {Keywords: IO model, Fine-grained Complexity, Algorithms}
}
|
Keywords: |
|
IO model, Fine-grained Complexity, Algorithms |
|
Collection: |
|
9th Innovations in Theoretical Computer Science Conference (ITCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
12.01.2018 |
