Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams, “Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy”, in Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Cambridge, Massachusetts, January 11–14, 2018, 34:1–34:23.

BibTeX

@InProceedings{FineGrainedCache_ITCS2018,
  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     = {Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  MONTH         = {January 11--14},
  YEAR          = 2018,
  ADDRESS       = {Cambridge, Massachusetts},
  PAGES         = {34:1--34:23},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.ITCS.2018.34},
  dblp          = {https://dblp.org/rec/conf/innovations/DemaineLLLW18},
  comments      = {The full version of this paper is available as
                   <A HREF="https://arXiv.org/abs/1711.07960">arXiv:1711.07960</A>, and from <A HREF="https://doi.org/10.4230/LIPIcs.ITCS.2018.34">LIPIcs</A>.},
}

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 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|²/(M B)) cache misses, which for sparse graphs improves over the previous O(|V|²/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 the relationship between “I/O linear time” Θ(n/B) and RAM linear time Θ(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.

Comments:

The full version of this paper is available as arXiv:1711.07960, and from LIPIcs.

Availability:

The paper is available in PDF (502k).

See information on file formats.

[Google Scholar search]