Document Open Access Logo

Fine-Grained Reductions and Quantum Speedups for Dynamic Programming

Author Amir Abboud

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.8.pdf
  • Filesize: 467 kB
  • 13 pages

Document Identifiers

Author Details

Amir Abboud
  • IBM Almaden Research Center, San Jose, California, USA

Funding

We acknowledge the support of the Quantum Computing Sciences program of the U.S. Air Force, Office of Scientific Research, administered through Air Force Research Laboratory contract FA8750-18-C-0098.

Acknowledgements

We thank Karl Bringmann and the anonymous reviewers for helpful feedback.

Cite AsGet BibTex

Amir Abboud. Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.8

Abstract

This paper points at a connection between certain (classical) fine-grained reductions and the question: Do quantum algorithms offer an advantage for problems whose (classical) best solution is via dynamic programming? A remarkable recent result of Ambainis et al. [SODA 2019] indicates that the answer is positive for some fundamental problems such as Set-Cover and Travelling Salesman. They design a quantum O^*(1.728^n) time algorithm whereas the dynamic programming O^*(2^n) time algorithms are conjectured to be classically optimal. In this paper, fine-grained reductions are extracted from their algorithms giving the first lower bounds for problems in P that are based on the intriguing Set-Cover Conjecture (SeCoCo) of Cygan et al. [CCC 2010]. In particular, the SeCoCo implies: - a super-linear Omega(n^{1.08}) lower bound for 3-SUM on n integers, - an Omega(n^{k/(c_k)-epsilon}) lower bound for k-SUM on n integers and k-Clique on n-node graphs, for any integer k >= 3, where c_k <= log_2{k}+1.4427. While far from being tight, these lower bounds are significantly stronger than what is known to follow from the Strong Exponential Time Hypothesis (SETH); the well-known n^{Omega(k)} ETH-based lower bounds for k-Clique and k-SUM are vacuous when k is constant. Going in the opposite direction, this paper observes that some "sequential" problems with previously known fine-grained reductions to a "parallelizable" core also enjoy quantum speedups over their classical dynamic programming solutions. Examples include RNA Folding and Least-Weight Subsequence.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Fine-Grained Complexity
  • Set-Cover
  • 3-SUM
  • k-Clique
  • k-SUM
  • Dynamic Programming
  • Quantum 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. Tight Hardness Results for LCS and other Sequence Similarity Measures. In Proc. of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 59-78, 2015. Google Scholar
  2. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 41-57, 2019. Google Scholar
  3. Amir Abboud and Kevin Lewi. Exact Weight Subgraphs and the k-sum Conjecture. In Proc. of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 1-12, 2013. Google Scholar
  4. Amir Abboud, Kevin Lewi, and R. Ryan Williams. Losing Weight by Gaining Edges. In Proc. of the 22th annual European Symposium on Algorithms (ESA), pages 1-12, 2014. Google Scholar
  5. Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs. Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1783-1793, 2019. Google Scholar
  6. Andreas Björklund, Holger Dell, and Thore Husfeldt. The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 231-242, 2015. Google Scholar
  7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci., 87:119-139, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2017.03.003.
  8. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set Partitioning via Inclusion-Exclusion. SIAM J. Comput., 39(2):546-563, 2009. URL: http://dx.doi.org/10.1137/070683933.
  9. Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Constrained Multilinear Detection and Generalized Graph Motifs. Algorithmica, 74(2):947-967, 2016. URL: http://dx.doi.org/10.1007/s00453-015-9981-1.
  10. Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams. Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 375-384, 2016. Google Scholar
  11. 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 Proc. of the 7th ACM Conference on Innovations in Theoretical Computer Science (ITCS), pages 261-270, 2016. Google Scholar
  12. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput., 201(2):216-231, 2005. Google Scholar
  13. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci., 72(8):1346-1367, 2006. Google Scholar
  14. Lijie Chen and Ruosong Wang. Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 23:1-23:20, 2019. Google Scholar
  15. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Transactions on Algorithms, 12(3):41, 2016. Google Scholar
  16. Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk. On problems equivalent to (min,+)-convolution. ACM Transactions on Algorithms (TALG), 15(1):14, 2019. Google Scholar
  17. Christoph Dürr and Peter Høyer. A Quantum Algorithm for Finding the Minimum. CoRR, quant-ph/9607014, 1996. URL: http://arxiv.org/abs/quant-ph/9607014.
  18. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1):57-67, 2004. Google Scholar
  19. Fedor V Fomin, Dieter Kratsch, and Gerhard J Woeginger. Exact (exponential) algorithms for the dominating set problem. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 245-256. Springer, 2004. Google Scholar
  20. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Computational Geometry, 5(3):165-185, 1995. Google Scholar
  21. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303, 2014. Google Scholar
  22. Lov K Grover. A fast quantum mechanical algorithm for database search. arXiv preprint, 1996. URL: http://arxiv.org/abs/quant-ph/9605043.
  23. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  24. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  25. Kamil Khadiev. Quantum Dynamic Programming Algorithm for DAGs. Applications for AND-OR DAG Evaluation and DAG’s Diameter Search. CoRR, abs/1804.09950, 2018. URL: http://arxiv.org/abs/1804.09950.
  26. Lukasz Kowalik and Juho Lauri. On finding rainbow and colorful paths. Theor. Comput. Sci., 628:110-114, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.03.017.
  27. Robert Krauthgamer and Ohad Trabelsi. The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern. arXiv preprint, 2017. URL: http://arxiv.org/abs/1711.08041.
  28. R Krithika, Abhishek Sahu, and Prafullkumar Tale. Dynamic parameterized problems. Algorithmica, 80(9):2637-2655, 2018. Google Scholar
  29. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 21:1-21:15, 2017. Google Scholar
  30. Aran Nayebi and Virginia Vassilevska Williams. Quantum algorithms for shortest paths problems in structured instances. CoRR, abs/1410.6220, 2014. URL: http://arxiv.org/abs/1410.6220.
  31. Jesper Nederlof. Finding Large Set Covers Faster via the Representation Method. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 69:1-69:15, 2016. Google Scholar
  32. J. Nešetřil and S. Poljak. On the complexity of the subgraph problem. Commentationes Math. Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  33. Mihai Pătraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1065-1075. SIAM, 2010. Google Scholar
  34. Ohad Trabelsi. Nearly Optimal Time Bounds for kPath in Hypergraphs. CoRR, abs/1803.04940, 2018. URL: http://arxiv.org/abs/1803.04940.
  35. Leslie G. Valiant. General Context-Free Recognition in Less than Cubic Time. J. Comput. Syst. Sci., 10(2):308-315, 1975. URL: http://dx.doi.org/10.1016/S0022-0000(75)80046-8.
  36. R. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2-3):357-365, 2005. Google Scholar
  37. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. Google Scholar
  38. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th symposium on Theory of Computing, pages 887-898. ACM, 2012. Google Scholar
  39. Virginia Vassilevska Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk). In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, pages 17-29, 2015. Google Scholar
  40. Virginia Vassilevska Williams. Some Open Problems in Fine-Grained Complexity. SIGACT News, 49(4):29-35, 2018. URL: http://dx.doi.org/10.1145/3300150.3300158.
  41. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems. J. ACM, 65(5):27:1-27:38, 2018. URL: http://dx.doi.org/10.1145/3186893.
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 Imprint Privacy Contact