How Hard is it to Find (Honest) Witnesses?

Authors Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat



PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.45.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Isaac Goldstein
Tsvi Kopelowitz
Moshe Lewenstein
Ely Porat

Cite AsGet BibTex

Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. How Hard is it to Find (Honest) Witnesses?. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.45

Abstract

In recent years much effort has been put into developing polynomial-time conditional lower bounds for algorithms and data structures in both static and dynamic settings. Along these lines we introduce a framework for proving conditional lower bounds based on the well-known 3SUM conjecture. Our framework creates a compact representation of an instance of the 3SUM problem using hashing and domain specific encoding. This compact representation admits false solutions to the original 3SUM problem instance which we reveal and eliminate until we find a true solution. In other words, from all witnesses (candidate solutions) we figure out if an honest one (a true solution) exists. This enumeration of witnesses is used to prove conditional lower bounds on reporting problems that generate all witnesses. In turn, these reporting problems are then reduced to various decision problems using special search data structures which are able to enumerate the witnesses while only using solutions to decision variants. Hence, 3SUM-hardness of the decision problems is deduced. We utilize this framework to show conditional lower bounds for several variants of convolutions, matrix multiplication and string problems. Our framework uses a strong connection between all of these problems and the ability to find witnesses. Specifically, we prove conditional lower bounds for computing partial outputs of convolutions and matrix multiplication for sparse inputs. These problems are inspired by the open question raised by Muthukrishnan 20 years ago. The lower bounds we show rule out the possibility (unless the 3SUM conjecture is false) that almost linear time solutions to sparse input-output convolutions or matrix multiplications exist. This is in contrast to standard convolutions and matrix multiplications that have, or assumed to have, almost linear solutions. Moreover, we improve upon the conditional lower bounds of Amir et al. for histogram indexing, a problem that has been of much interest recently. The conditional lower bounds we show apply for both reporting and decision variants. For the well-studied decision variant, we show a full tradeoff between preprocessing and query time for every alphabet size > 2. At an extreme, this implies that no solution to this problem exists with subquadratic preprocessing time and ~O(1) query time for every alphabet size > 2, unless the 3SUM conjecture is false. This is in contrast to a recent result by Chan and Lewenstein for a binary alphabet. While these specific applications are used to demonstrate the techniques of our framework, we believe that this novel framework is useful for many other problems as well.
Keywords
  • 3SUM
  • convolutions
  • matrix multiplication
  • histogram indexing

Metrics

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

References

  1. Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In Int'l Colloquium on Automata, Languages and Programming, ICALP 2013, pages 1-12, 2013. Google Scholar
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Foundations of Computer Science, FOCS 2014, pages 434-443, 2014. Google Scholar
  3. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In International Colloquium on Automata, Languages and Programming, ICALP 2014, pages 39-51, 2014. Google Scholar
  4. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Symposium on Theory of Computing, STOC 2015, pages 41-50, 2015. Google Scholar
  5. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In International Colloquium on Automata, Languages and Programming, ICALP 2014, pages 114-125, 2014. Google Scholar
  6. Ilya Baran, Erik D. Demaine, and Mihai Patrascu. Subquadratic algorithms for 3SUM. In Workshop on Algorithms and Data Structures, WADS 2005, pages 409-421, 2005. Google Scholar
  7. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. Google Scholar
  8. Peter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. Algorithms for jumbled pattern matching in strings. Int. J. Found. Comput. Sci., 23(2):357-374, 2012. Google Scholar
  9. Timothy Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Symposium on Theory of Computing, STOC 2015, pages 31-40, 2015. Google Scholar
  10. Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. Searching for jumbled patterns in strings. In Prague Stringology Conference, pages 105-117, 2009. Google Scholar
  11. Richard Cole and Ramesh Hariharan. Verifying candidate matches in sparse and wildcard matching. In Symposium on Theory of Computing, STOC 2002, pages 592-601, 2002. Google Scholar
  12. Martin Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In Symposium on Theoretical Aspects of Computer Science, STACS 1996, pages 569-580, 1996. Google Scholar
  13. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. Google Scholar
  14. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC 2014, pages 296-303, 2014. Google Scholar
  15. Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Nearly optimal sparse fourier transform. In Symposium on Theory of Computing Conference, STOC 2012, pages 563-578, 2012. Google Scholar
  16. Danny Hermelin, Gad M. Landau, Yuri Rabinovich, and Oren Weimann. Binary jumbled pattern matching via all-pairs shortest paths. CoRR, abs/1401.2065, 2014. Google Scholar
  17. Allan Grønlund Jørgensen and Seth Pettie. Threesomes, degenerates, and love triangles. In Foundations of Computer Science, FOCS 2014, pages 621-630, 2014. Google Scholar
  18. Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter. Efficient indexes for jumbled pattern matching with constant-sized alphabet. In ESA, pages 625-636, 2013. Google Scholar
  19. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In Symposium on Discrete Algorithms, SODA 2016, pages 1272-1287, 2016. Google Scholar
  20. Tanaeem M. Moosa and M. Sohel Rahman. Indexing permutations for binary strings. Inf. Process. Lett., 110(18-19):795-798, 2010. Google Scholar
  21. Tanaeem M. Moosa and M. Sohel Rahman. Sub-quadratic time and linear space data structures for permutation matching in binary strings. J. Discrete Algorithms, 10:5-9, 2012. Google Scholar
  22. S. Muthukrishnan. New results and open problems related to non-standard stringology. In CPM 1995, pages 298-317, 1995. Google Scholar
  23. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Symposium on Theory of Computing Conference, STOC 2010, pages 603-610, 2010. Google Scholar
  24. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Symposium on Theory of Computing, STOC 2014, pages 664-673, 2014. Google Scholar
  25. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Symposium on Theory of Computing Conference, STOC 2012, pages 887-898, 2012. 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