Document Open Access Logo

Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy

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

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.34.pdf
  • Filesize: 0.63 MB
  • 23 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

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 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.34

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.

Subject Classification

Keywords
  • IO model
  • Fine-grained Complexity
  • Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 98-117, Berkeley, CA, October 2015. Google Scholar
  2. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pages 1681-1697, San Diego, CA, January 2015. Google Scholar
  3. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 434-443, 2014. Google Scholar
  4. Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 377-391, 2016. Google Scholar
  5. Alok Aggarwal and S. Vitter, Jeffrey. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116-1127, 1988. Google Scholar
  6. Lars Arge. External-memory algorithms with applications in gis. In Algorithmic Foundations of Geographic Information Systems, This Book Originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, pages 213-254, 1997. URL: http://dl.acm.org/citation.cfm?id=648260.753061.
  7. Lars Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1-24, 2003. URL: http://dx.doi.org/10.1007/s00453-003-1021-x.
  8. Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro. An optimal cache-oblivious priority queue and its application to graph algorithms. SIAM J. Comput., 36(6):1672-1695, 2007. URL: http://dx.doi.org/10.1137/S0097539703428324.
  9. Lars Arge, Ulrich Meyer, and Laura Toma. External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs. In Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella, editors, Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, volume 3142 of Lecture Notes in Computer Science, pages 146-157. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27836-8_15.
  10. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless seth is false). In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, pages 51-58, 2015. Google Scholar
  11. Boaz Barak. A probabilistic-time hierarchy theorem for "slightly non-uniform" algorithms. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, RANDOM 2002, pages 194-208, Cambridge, MA, September 2002. Google Scholar
  12. Ilya Baran, Erik D Demaine, and Mihai Pǎtraşcu. Subquadratic algorithms for 3sum. In Workshop on Algorithms and Data Structures, pages 409-421, 2005. Google Scholar
  13. R. Bayer and E. McCreight. Organization and maintenance of large ordered indices. In Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, SIGFIDET '70, pages 107-141, 1970. URL: http://dx.doi.org/10.1145/1734663.1734671.
  14. Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito. Two simplified algorithms for maintaining order in a list. In Proceedings of the 10th Annual European Symposium on Algorithms, ESA 2002, pages 152-164, 2002. URL: http://dl.acm.org/citation.cfm?id=647912.740822.
  15. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 661-670, Philadelphia, PA, October 2014. Google Scholar
  16. Gerth Stølting Brodal. Cache-oblivious algorithms and data structures. In Torben Hagerup and Jyrki Katajainen, editors, Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings, volume 3111 of Lecture Notes in Computer Science, pages 3-13. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27810-8_2.
  17. Yi-Jen Chiang, Michael T Goodrich, Edward F Grove, Roberto Tamassia, Darren Erik Vengroff, and Jeffrey Scott Vitter. External-memory graph algorithms. In SODA, volume 95, pages 139-149, 1995. Google Scholar
  18. Rezaul Alam Chowdhury and Vijaya Ramachandran. Cache-oblivious shortest paths in graphs using buffer heap. In Phillip B. Gibbons and Micah Adler, editors, SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, June 27-30, 2004, Barcelona, Spain, pages 245-254. ACM, 2004. URL: http://dx.doi.org/10.1145/1007912.1007949.
  19. Rezaul Alam Chowdhury and Vijaya Ramachandran. External-memory exact and approximate all-pairs shortest-paths in undirected graphs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 735-744, 2005. Google Scholar
  20. Rezaul Alam Chowdhury and Vijaya Ramachandran. Cache-oblivious dynamic programming. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 591-600, 2006. Google Scholar
  21. Rezaul Alam Chowdhury and Vijaya Ramachandran. Cache-oblivious dynamic programming. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 591-600, 2006. Google Scholar
  22. Stephen A. Cook and Robert A. Reckhow. Time-bounded random access machines. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing, pages 73-80, 1972. Google Scholar
  23. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251-280, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80013-2.
  24. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  25. Erik D. Demaine. Cache-oblivious algorithms and data structures. Lecture Notes from the EEF Summer School on Massive Data Sets, 2002. Google Scholar
  26. Roman Dementiev. Algorithm engineering for large data sets. PhD thesis, Saarland University, 2006. Google Scholar
  27. Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th Annual Symposium on the Foundations of Computer Science (FOCS), pages 285-298, 1999. Google Scholar
  28. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC 2014, Kobe, Japan, July 23-25, 2014, pages 296-303, 2014. Google Scholar
  29. Jia-Wei Hong and H. T. Kung. I/O complexity: The red-blue pebble game. In Proceedings of the 13th Annual ACM Symposium on the Theory of Computation (STOC), pages 326-333, 1981. Google Scholar
  30. Kurt Mehlhorn and Ulrich Meyer. External-memory breadth-first search with sublinear I/O. In Rolf H. Möhring and Rajeev Raman, editors, Algorithms - ESA 2002, 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings, volume 2461 of Lecture Notes in Computer Science, pages 723-735. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45749-6_63.
  31. Bruno Menegola. An external memory algorithm for listing triangles. Bachelor’s thesis, Universidade Federal do Rio Grande do Sul, 2010. URL: http://hdl.handle.net/10183/26335.
  32. Ulrich Meyer and Norbert Zeh. I/o-efficient undirected shortest paths. In Giuseppe Di Battista and Uri Zwick, editors, Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings, volume 2832 of Lecture Notes in Computer Science, pages 434-445. Springer, 2003. URL: http://dx.doi.org/10.1007/978-3-540-39658-1_40.
  33. Rasmus Pagh and Francesco Silvestri. The input/output complexity of triangle enumeration. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 224-233, 2014. Google Scholar
  34. Rasmus Pagh and Morten Stöckel. The input/output complexity of sparse matrix multiplication. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 750-761. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_62.
  35. Mihai Pǎtraşcu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 603-610, 2010. Google Scholar
  36. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th Symposium on Theory of Computing Conference, STOC 2013, pages 515-524, Palo Alto, CA, June 2013. Google Scholar
  37. Raimund Seidel. On the all-pairs-shortest-path problem. In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 745-749. ACM, 1992. URL: http://dx.doi.org/10.1145/129712.129784.
  38. Michael Sipser. Introduction to the Theory of Computation, volume 2. Thomson Course Technology Boston, 2006. Google Scholar
  39. Robert I. Soare. Recursively enumerable sets and degrees: A study of computable functions and computably generated sets. Springer Science &Business Media, 1999. Google Scholar
  40. A. M. Turing. Systems of logic based on ordinals. Proceedings of the London Mathematical Society, s2-45(1):161-228, 1939. Google Scholar
  41. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In STOC, pages 887-898, 2012. Google Scholar
  42. Jeffrey Scott Vitter. External memory algorithms and data structures. ACM Comput. Surv., 33(2):209-271, 2001. URL: http://dx.doi.org/10.1145/384192.384193.
  43. Ryan Williams. Hierarchy for BPP vs derandomization. Theoretical Computer Science Stack Exchange. URL: http://cstheory.stackexchange.com/q/6769.
  44. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 645-654, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact