Document Open Access Logo

Fine-Grained Complexity Theory (Tutorial)

Author Karl Bringmann

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.4.pdf
  • Filesize: 393 kB
  • 7 pages

Document Identifiers

Author Details

Karl Bringmann
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Cite As Get BibTex

Karl Bringmann. Fine-Grained Complexity Theory (Tutorial). In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 4:1-4:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.4

Abstract

Suppose the fastest algorithm that we can design for some problem runs in time O(n^2). However, we want to solve the problem on big data inputs, for which quadratic time is impractically slow. We can keep searching for a faster algorithm, but maybe none exists. Is there any reasoning that provides evidence against significantly faster algorithms, and thus allows us to stop searching? In other words, is there an analogue of NP-hardness for polynomial-time problems?
In this tutorial, we will give an introduction to fine-grained complexity theory, which allows to rule out faster algorithms by proving conditional lower bounds via fine-grained reductions from certain key conjectures. We will define these terms and show exemplary lower bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Hardness in P
  • conditional lower bound
  • fine-grained reduction

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. In FOCS, pages 192-203, 2017. Google Scholar
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the Current Clique Algorithms are Optimal, So is Valiant’s Parser. In FOCS, pages 98-117, 2015. Google Scholar
  3. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In FOCS, pages 59-78, 2015. Google Scholar
  4. Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof. More consequences of falsifying SETH and the orthogonal vectors conjecture. In STOC, pages 253-266. ACM, 2018. Google Scholar
  5. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-based lower bounds for Subset Sum and Bicriteria Path. In SODA, 2019. To appear. See URL: https://arxiv.org/abs/1704.04546.
  6. Amir Abboud and Søren Dahlgaard. Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. In FOCS, pages 477-486, 2016. Google Scholar
  7. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends, or: a polylog shaved is a lower bound made. In STOC, pages 375-388, 2016. Google Scholar
  8. Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP Theorems for Hardness of Approximation in P. In FOCS, pages 25-36, 2017. Google Scholar
  9. Amir Abboud and Virginia Vassilevska Williams. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In FOCS, pages 434-443, 2014. Google Scholar
  10. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. In STOC, pages 41-50, 2015. Google Scholar
  11. Udit Agarwal and Vijaya Ramachandran. Fine-grained complexity for sparse graphs. In STOC, pages 239-252, 2018. Google Scholar
  12. Divesh Aggarwal and Noah Stephens-Davidowitz. (Gap/S)ETH hardness of SVP. In STOC, pages 228-238, 2018. Google Scholar
  13. Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). In STOC, pages 51-58, 2015. Google Scholar
  14. Arturs Backurs and Piotr Indyk. Which Regular Expression Patterns Are Hard to Match? In FOCS, pages 457-466, 2016. Google Scholar
  15. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In STOC, pages 267-280, 2018. Google Scholar
  16. R.E. Bellman. Dynamic programming. Princeton University Press, 1957. Google Scholar
  17. Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz. On the Quantitative Hardness of CVP. In FOCS, pages 13-24, 2017. Google Scholar
  18. Karl Bringmann. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In FOCS, pages 661-670, 2014. Google Scholar
  19. Karl Bringmann. A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. In SODA, pages 1073-1084. SIAM, 2017. Google Scholar
  20. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A Dichotomy for Regular Expression Membership Testing. In FOCS, pages 307-318, 2017. Google Scholar
  21. Karl Bringmann and Marvin Künnemann. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In FOCS, pages 79-97, 2015. Google Scholar
  22. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility. In ITCS, pages 261-270, 2016. Google Scholar
  23. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  24. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michał Włodarczyk. On Problems Equivalent to (min, +)-Convolution. In ICALP, volume 80 of LIPIcs, pages 22:1-22:15, 2017. Google Scholar
  25. Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting to decision. In STOC, pages 281-288, 2018. Google Scholar
  26. 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 ITCS, volume 94 of LIPIcs, pages 34:1-34:23, 2018. Google Scholar
  27. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. Google Scholar
  28. Robert W. Floyd. Algorithm 97: Shortest path. Commun. ACM, 5(6):345, 1962. Google Scholar
  29. Anka Gajentaan and Mark H. Overmars. On a Class of O(n²) Problems in Computational Geometry. Comput. Geom., 5:165-185, 1995. Google Scholar
  30. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In STOC, pages 21-30, 2015. Google Scholar
  31. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  32. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In ICALP, volume 80 of LIPIcs, pages 21:1-21:15, 2017. Google Scholar
  33. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 105:41-72, 2011. Google Scholar
  34. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515-524, 2013. Google Scholar
  35. Barna Saha. Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems. In FOCS, pages 118-135, 2015. Google Scholar
  36. Ken Thompson. Regular Expression Search Algorithm. Commun. ACM, 11(6):419-422, 1968. Google Scholar
  37. Virginia Vassilevska Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk). In IPEC, volume 43 of LIPIcs, pages 17-29, 2015. Google Scholar
  38. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In ICM, 2018. To appear. See URL: https://people.csail.mit.edu/virgi/eccentri.pdf.
  39. Virginia Vassilevska Williams and Ryan Williams. Subcubic Equivalences between Path, Matrix and Triangle Problems. In FOCS, pages 645-654, 2010. Google Scholar
  40. Stephen Warshall. A Theorem on Boolean Matrices. J. ACM, 9(1):11-12, 1962. Google Scholar
  41. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. Google Scholar
  42. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In STOC, pages 664-673, 2014. 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