Document Open Access Logo

Fine-Grained Hardness for Edit Distance to a Fixed Sequence

Authors Amir Abboud, Virginia Vassilevska Williams

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.7.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

Amir Abboud
  • Weizmann Institute of Science, Rehovot, Israel
Virginia Vassilevska Williams
  • MIT, Cambridge, MA, US

Funding

  • Abboud, Amir: Work partly done at the IBM Almaden Research Center.
  • Vassilevska Williams, Virginia: Supported by an NSF CAREER Award, NSF Grants CCF-1528078, CCF-1514339 and CCF-1909429, a BSF Grant BSF:2012338, a Google Research Fellowship and a Sloan Research Fellowship.

Cite As Get BibTex

Amir Abboud and Virginia Vassilevska Williams. Fine-Grained Hardness for Edit Distance to a Fixed Sequence. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.7

Abstract

Nearly all quadratic lower bounds conditioned on the Strong Exponential Time Hypothesis (SETH) start by reducing k-SAT to the Orthogonal Vectors (OV) problem: Given two sets A,B of n binary vectors, decide if there is an orthogonal pair a ∈ A, b ∈ B. In this paper, we give an alternative reduction in which the set A does not depend on the input to k-SAT; thus, the quadratic lower bound for OV holds even if one of the sets is fixed in advance.
Using the reductions in the literature from OV to other problems such as computing similarity measures on strings, we get hardness results of a stronger kind: there is a family of sequences {S_n}_{n = 1}^{∞}, |S_n| = n such that computing the Edit Distance between an input sequence X of length n and the (fixed) sequence S_n requires n^{2-o(1)} time under SETH.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • SAT
  • edit distance
  • fine-grained complexity
  • conditional lower bound
  • sequence alignment

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 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 192-203, 2017. Google Scholar
  2. Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Or Zamir. Subtree isomorphism revisited. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1256-1271, 2016. Google Scholar
  3. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for lcs and other sequence similarity measures. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 59-78. IEEE, 2015. Google Scholar
  4. Amir Abboud and Karl Bringmann. Tighter connections between formula-sat and shaving logs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.08978.
  5. Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof. More consequences of falsifying SETH and the orthogonal vectors conjecture. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 253-266, 2018. Google Scholar
  6. 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 Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 375-388, 2016. Google Scholar
  7. Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed pcp theorems for hardness of approximation in p. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 25-36. IEEE, 2017. Google Scholar
  8. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443, 2014. Google Scholar
  9. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 39-51, 2014. Google Scholar
  10. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. SIAM Journal on Computing, 47(3):1098-1122, 2018. Google Scholar
  11. Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 218-230. SIAM, 2014. Google Scholar
  12. Josh Alman and Ryan Williams. Probabilistic polynomials and hamming nearest neighbors. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 136-150. IEEE, 2015. Google Scholar
  13. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  14. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 51-58, 2015. Google Scholar
  15. Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 457-466. IEEE, 2016. Google Scholar
  16. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 267-280, 2018. Google Scholar
  17. Nikhil Bansal and Ryan Williams. Regularity lemmas and combinatorial algorithms. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 745-754. IEEE, 2009. Google Scholar
  18. Maria Luisa Bonet and Samuel R Buss. Size-depth tradeoffs for boolean formulae. Information Processing Letters, 49(3):151-155, 1994. Google Scholar
  19. Karl Bringman and Marvin Künnemann. Multivariate fine-grained complexity of longest common subsequence. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1216-1235. SIAM, 2018. Google Scholar
  20. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 661-670, 2014. Google Scholar
  21. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 307-318. IEEE, 2017. Google Scholar
  22. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 79-97. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.15.
  23. Karl Bringmann, Marvin Künnemann, and André Nusser. Fréchet distance under translation: conditional hardness and an algorithm via offline dynamic grid reachability. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2902-2921. SIAM, 2019. Google Scholar
  24. Timothy M Chan and Moshe Lewenstein. Clustered integer 3sum via additive combinatorics. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 31-40, 2015. Google Scholar
  25. Timothy M Chan and Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1246-1255. SIAM, 2016. Google Scholar
  26. Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N Rothblum, and Aviad Rubinstein. Fine-grained complexity meets ip= pspace. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-20. SIAM, 2019. Google Scholar
  27. Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 21-40. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.2.
  28. Karthik CS, Roee David, and Bundit Laekhanukit. On the complexity of closest pair via polar-pair of point-sets. SIAM Journal on Discrete Mathematics, 33(1):509-527, 2019. Google Scholar
  29. Karthik CS, Bundit Laekhanukit, and P Manurangsi. On the parameterized complexity of approximating dominating set. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1283-1296, 2018. Google Scholar
  30. Karthik CS and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic. ITCS, 2019. Google Scholar
  31. Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams. New techniques for proving fine-grained average-case hardness. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 774-785. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00077.
  32. Lech Duraj, Marvin Künnemann, and Adam Polak. Tight conditional lower bounds for longest common increasing subsequence. Algorithmica, 81(10):3968-3992, 2019. Google Scholar
  33. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(2):23:1-23:35, 2019. URL: https://doi.org/10.1145/3196275.
  34. Elazar Goldenberg, Aviad Rubinstein, and Barna Saha. Does preprocessing help in fast sequence comparisons? In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 657-670, 2020. Google Scholar
  35. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Workshop on Algorithms and Data Structures, pages 421-436. Springer, 2017. Google Scholar
  36. Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan. Data structures meet cryptography: 3sum with preprocessing. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 294-307, 2020. Google Scholar
  37. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21-30, 2015. Google Scholar
  38. Robert Krauthgamer and Ohad Trabelsi. Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4):1-15, 2018. Google Scholar
  39. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 515-524, 2013. Google Scholar
  40. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, 2018. Google Scholar
  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: https://doi.org/10.1145/3186893.
  42. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
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