Document Open Access Logo

Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds

Authors Amir Abboud, Aviad Rubinstein

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.35.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Amir Abboud
Aviad Rubinstein

Cite As Get BibTex

Amir Abboud and Aviad Rubinstein. Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.35

Abstract

The Longest Common Subsequence (LCS) is one of the most basic similarity measures and it captures important applications in bioinformatics and text analysis. Following the SETH-based nearly-quadratic time lower bounds for LCS from recent years, it is a major open problem to understand the complexity of approximate LCS.
In the last ITCS [AB17] drew an interesting connection between this problem and the area of circuit complexity:
they proved that approximation algorithms for LCS in deterministic truly-subquadratic time imply new circuit lower bounds (E^NP does not have non-uniform linear-size Valiant Series Parallel circuits).

In this work, we strengthen this connection between approximate LCS and circuit complexity by applying the Distributed PCP framework of [ARW17]. 
We obtain a reduction that holds against much larger approximation factors (super-constant versus 1+o(1)), yields a lower bound for a larger class of circuits (linear-size NC^1), and is also easier to analyze.

Subject Classification

Keywords
  • Distributed PCP
  • Longest Common Subsequence
  • Fine-grained Complexity
  • Strong Exponential Time Hypothesis

Metrics

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

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. TOCT, 1(1):2:1-2:54, 2009. URL: http://dx.doi.org/10.1145/1490270.1490272.
  2. Amir Abboud and Arturs Backurs. Towards hardness of approximation for polynomial time problems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 11:1-11:26. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2017.11.
  3. Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 192-203. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.26.
  4. 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
  5. 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 Proc. of the 48th STOC, pages 375-388, 2016. Google Scholar
  6. Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 25-36. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.12.
  7. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Proc. of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 39-51, 2014. Google Scholar
  8. Stephen F Altschul, Thomas L Madden, Alejandro A Schäffer, Jinghui Zhang, Zheng Zhang, Webb Miller, and David J Lipman. Gapped blast and psi-blast: a new generation of protein database search programs. Nucleic acids research, 25(17):3389-3402, 1997. Google Scholar
  9. Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Polylogarithmic approximation for edit distance and the asymmetric query complexity. In FOCS, pages 377-386, 2010. Google Scholar
  10. Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). In Proc. of the 47th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 51-58, 2015. Google Scholar
  11. Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In Proc. of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 457-466, 2016. Google Scholar
  12. Ziv Bar-Yossef, TS Jayram, Robert Krauthgamer, and Ravi Kumar. Approximating edit distance efficiently. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 550-559. IEEE, 2004. Google Scholar
  13. Tuğkan Batu, Funda Ergun, and Cenk Sahinalp. Oblivious string embeddings and edit distance approximations. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 792-801. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  14. Paul Beame. Lecture notes on circuit reducibility, depth reduction, and parallel arithmetic, April 2008. Google Scholar
  15. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Short interactive oracle proofs with constant query complexity, via composition and sumcheck. IACR Cryptology ePrint Archive, 2016:324, 2016. URL: http://eprint.iacr.org/2016/324.
  16. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II, volume 9986 of Lecture Notes in Computer Science, pages 31-60, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53644-5_2.
  17. Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth. Constant rate pcps for circuit-sat with sublinear query complexity. J. ACM, 63(4):32:1-32:57, 2016. URL: http://dx.doi.org/10.1145/2901294.
  18. Eli Ben-Sasson and Emanuele Viola. Short pcps with projection queries. In ICALP, Part I, pages 163-173, 2014. Google Scholar
  19. Lasse Bergroth, Harri Hakonen, and Timo Raita. New approximation algorithms for longest common subsequences. In String Processing and Information Retrieval: A South American Symposium, 1998. Proceedings, pages 32-40. IEEE, 1998. Google Scholar
  20. Lasse Bergroth, Harri Hakonen, and Timo Raita. A survey of longest common subsequence algorithms. In String Processing and Information Retrieval, 2000. SPIRE 2000. Proceedings. Seventh International Symposium on, pages 39-48. IEEE, 2000. Google Scholar
  21. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 307-318. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.36.
  22. Karl Bringmann and Marvin Kunnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proc. of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 79-97, 2015. Google Scholar
  23. Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký. Streaming algorithms for embedding and computing edit distance in the low distance regime. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 712-725. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897577.
  24. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-eth to fpt-inapproximability: Clique, dominating set, and more. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 743-754. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.74.
  25. F Chin and Chung Keung Poon. Performance analysis of some simple heuristics for computing longest common subsequences. Algorithmica, 12(4-5):293-311, 1994. Google Scholar
  26. Maxime Crochemore, Costas S Iliopoulos, Yoan J Pinzon, and James F Reid. A fast and practical bit-vector algorithm for the longest common subsequence problem. Information Processing Letters, 80(6):279-285, 2001. Google Scholar
  27. J Boutet de Monvel. Extensive simulations for longest common subsequences. The European Physical Journal B-Condensed Matter and Complex Systems, 7(2):293-308, 1999. Google Scholar
  28. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. URL: http://dx.doi.org/10.1145/1236457.1236459.
  29. Irit Dinur. Mildly exponential reduction from gap 3sat to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016. URL: http://eccc.hpi-web.de/report/2016/128.
  30. Andrew Drucker. PCPs for Arthur-Merlin Games and Communication Protocols. Master’s thesis, Massachusetts Institute of Technology, 2010. URL: http://people.csail.mit.edu/andyd/Drucker_SM_thesis.pdf.
  31. Paweł Gawrychowski. Faster algorithm for computing the edit distance between slp-compressed strings. In International Symposium on String Processing and Information Retrieval, pages 229-236. Springer, 2012. Google Scholar
  32. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27:1-27:64, 2015. URL: http://dx.doi.org/10.1145/2699436.
  33. Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. Interactive locking, zero-knowledge pcps, and unconditional cryptography. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 173-190. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14623-7_10.
  34. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672-694, 2002. Google Scholar
  35. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  36. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  37. Hamid Jahanjou, Eric Miles, and Emanuele Viola. Local reductions. In International Colloquium on Automata, Languages, and Programming, pages 749-760. Springer, 2015. Google Scholar
  38. Yael Tauman Kalai and Ran Raz. Interactive PCP. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, volume 5126 of Lecture Notes in Computer Science, pages 536-547. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70583-3_44.
  39. Gad M Landau, Eugene W Myers, and Jeanette P Schmidt. Incremental string comparison. SIAM Journal on Computing, 27(2):557-582, 1998. Google Scholar
  40. Pasin Manurangsi. Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 954-961. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055412.
  41. Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense csps. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 78:1-78:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.78.
  42. Thilo Mie. Short pcpps verifiable in polylogarithmic time with o (1) queries. Annals of Mathematics and Artificial Intelligence, 56(3-4):313-338, 2009. Google Scholar
  43. Gonzalo Navarro. A guided tour to approximate string matching. ACM computing surveys (CSUR), 33(1):31-88, 2001. Google Scholar
  44. Rafail Ostrovsky and Yuval Rabani. Low distortion embeddings for edit distance. Journal of the ACM (JACM), 54(5):23, 2007. Google Scholar
  45. Mihai Patrascu and Ryan Williams. On the possibility of faster SAT algorithms. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1065-1075. SIAM, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.86.
  46. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 49-62. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897652.
  47. Balaram Saha. The dyck language edit distance problem in near-linear time. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 611-620. IEEE, 2014. Google Scholar
  48. Barna Saha. Language edit distance and maximum likelihood parsing of stochastic grammars: Faster algorithms and connection to fundamental graph problems. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 118-135. IEEE, 2015. Google Scholar
  49. Barna Saha. Fast & space-efficient approximations of language edit distance and RNA folding: An amnesic dynamic programming approach. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 295-306. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.35.
  50. Rajesh Santhanam and Ross Williams. On medium-uniformity and circuit lower bounds. In Computational Complexity (CCC), 2013 IEEE Conference on, pages 15-23. IEEE, 2013. Google Scholar
  51. Leslie G Valiant. Graph-theoretic arguments in low-level complexity. Springer, 1977. Google Scholar
  52. 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
  53. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM Journal on Computing, 42(3):1218-1244, 2013. 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