Document Open Access Logo

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Author Lijie Chen

PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.14.pdf
  • Filesize: 0.79 MB
  • 45 pages

Document Identifiers

Author Details

Lijie Chen
  • Massachusetts Institute of Technology, USA

Funding

  • Chen, Lijie: Supported by an Akamai Fellowship

Cite As Get BibTex

Lijie Chen. On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 14:1-14:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CCC.2018.14

Abstract

In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets A and B of vectors, and the goal is to find a in A and b in B maximizing inner product a * b. Max-IP is very basic and serves as the base problem in the recent breakthrough of [Abboud et al., FOCS 2017] on hardness of approximation for polynomial-time problems. It is also used (implicitly) in the argument for hardness of exact l_2-Furthest Pair (and other important problems in computational geometry) in poly-log-log dimensions in [Williams, SODA 2018]. We have three main results regarding this problem.
- Characterization of Multiplicative Approximation. First, we study the best multiplicative approximation ratio for Boolean Max-IP in sub-quadratic time. We show that, for Max-IP with two sets of n vectors from {0,1}^{d}, there is an n^{2 - Omega(1)} time (d/log n)^{Omega(1)}-multiplicative-approximating algorithm, and we show this is conditionally optimal, as such a (d/log n)^{o(1)}-approximating algorithm would refute SETH. Similar characterization is also achieved for additive approximation for Max-IP.
- 2^{O(log^* n)}-dimensional Hardness for Exact Max-IP Over The Integers. Second, we revisit the hardness of solving Max-IP exactly for vectors with integer entries. We show that, under SETH, for Max-IP with sets of n vectors from Z^{d} for some d = 2^{O(log^* n)}, every exact algorithm requires n^{2 - o(1)} time. With the reduction from [Williams, SODA 2018], it follows that l_2-Furthest Pair and Bichromatic l_2-Closest Pair in 2^{O(log^* n)} dimensions require n^{2 - o(1)} time.
- Connection with NP * UPP Communication Protocols. Last, We establish a connection between conditional lower bounds for exact Max-IP with integer entries and NP * UPP communication protocols for Set-Disjointness, parallel to the connection between conditional lower bounds for approximating Max-IP and MA communication protocols for Set-Disjointness.
The lower bound in our first result is a direct corollary of the new MA protocol for Set-Disjointness introduced in [Rubinstein, STOC 2018], and our algorithms utilize the polynomial method and simple random sampling. Our second result follows from a new dimensionality self reduction from the Orthogonal Vectors problem for n vectors from {0,1}^{d} to n vectors from Z^{l} where l = 2^{O(log^* d)}, dramatically improving the previous reduction in [Williams, SODA 2018]. The key technical ingredient is a recursive application of Chinese Remainder Theorem.
As a side product, we obtain an MA communication protocol for Set-Disjointness with complexity O (sqrt{n log n log log n}), slightly improving the O (sqrt{n} log n) bound [Aaronson and Wigderson, TOCT 2009], and approaching the Omega(sqrt{n}) lower bound [Klauck, CCC 2003].
Moreover, we show that (under SETH) one can apply the O(sqrt{n}) BQP communication protocol for Set-Disjointness to prove near-optimal hardness for approximation to Max-IP with vectors in {-1,1}^d. This answers a question from [Abboud et al., FOCS 2017] in the affirmative.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Maximum Inner Product
  • SETH
  • Hardness of Approximation in P
  • Fined-Grained Complexity
  • Hopcroft's Problem
  • Chinese Remainder Theorem

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 LIPIcs-Leibniz International Proceedings in Informatics, volume 67. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  3. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, pages 477-486, 2016. Google Scholar
  4. Amir Abboud and Aviad Rubinstein. Fast and deterministic constant factor approximation algorithms for lcs imply new circuit lower bounds. In LIPIcs-Leibniz International Proceedings in Informatics, volume 94. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  5. 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.
  6. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. of the 55th FOCS, pages 434-443, 2014. Google Scholar
  7. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Proc. of the 41st ICALP, pages 39-51, 2014. Google Scholar
  8. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 41-50. ACM, 2015. Google Scholar
  9. 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. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  10. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, pages 434-443, 2014. Google Scholar
  11. Pankaj K Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete &Computational Geometry, 6(3):407-422, 1991. Google Scholar
  12. Thomas Dybdahl Ahle, Rasmus Pagh, Ilya Razenshteyn, and Francesco Silvestri. On the complexity of inner product similarity join. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 151-164. ACM, 2016. Google Scholar
  13. Josh Alman, Timothy M Chan, and Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 467-476. IEEE, 2016. Google Scholar
  14. Josh Alman and Ryan Williams. Probabilistic polynomials and hamming nearest neighbors. In Proc. of the 56th FOCS, pages 136-150. IEEE, 2015. Google Scholar
  15. Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In Proc. of the 47th FOCS, pages 459-468. IEEE, 2006. Google Scholar
  16. Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal lsh for angular distance. In Advances in Neural Information Processing Systems, pages 1225-1233, 2015. Google Scholar
  17. Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proc. of the 25th SODA, pages 1018-1028. SIAM, 2014. Google Scholar
  18. Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proc. of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 793-801. ACM, 2015. Google Scholar
  19. Tom M. Apostol. Introduction to analytic number theory. Springer Science &Business Media, 2013. Google Scholar
  20. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  21. 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
  22. 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
  23. Jon Louis Bentley and Michael Ian Shamos. Divide-and-conquer in multidimensional space. In Proceedings of the eighth annual ACM symposium on Theory of computing, pages 220-230. ACM, 1976. Google Scholar
  24. 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
  25. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 661-670, 2014. Google Scholar
  26. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. arXiv preprint arXiv:1611.00918, 2016. Google Scholar
  27. Harry Buhrman, Richard Cleve, Ronald De Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 358-368. IEEE, 1999. Google Scholar
  28. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 63-68. ACM, 1998. Google Scholar
  29. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In IWPEC, volume 5917, pages 75-85. Springer, 2009. Google Scholar
  30. Timothy M Chan. A (slightly) faster algorithm for klee’s measure problem. In Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 94-100. ACM, 2008. Google Scholar
  31. Tobias Christiani. A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In Proc. of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 31-46. SIAM, 2017. Google Scholar
  32. Tobias Christiani and Rasmus Pagh. Set similarity search beyond minhash. arXiv preprint arXiv:1612.07710, 2016. Google Scholar
  33. Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM Journal on Computing, 11(3):467-471, 1982. Google Scholar
  34. Svyatoslav Covanov and Emmanuel Thomé. Fast integer multiplication using generalized fermat primes. arXiv preprint arXiv:1502.02800, 2015. Google Scholar
  35. Roee David, CS Karthik, and Bundit Laekhanukit. On the complexity of closest pair via polar-pair of point-sets. CoRR, abs/1608.03245, 2016. Google Scholar
  36. Ronald de Wolf. A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions. arXiv preprint arXiv:0802.1816, 2008. Google Scholar
  37. Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19-51, 1997. Google Scholar
  38. Martin Fürer. Faster integer multiplication. SIAM Journal on Computing, 39(3):979-1005, 2009. Google Scholar
  39. Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029-1046. SIAM, 2018. Google Scholar
  40. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2162-2181, 2017. Google Scholar
  41. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, pages 421-436, Cham, 2017. Springer International Publishing. Google Scholar
  42. Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219. ACM, 1996. Google Scholar
  43. David Harvey, Joris Van Der Hoeven, and Grégoire Lecerf. Even faster integer multiplication. Journal of Complexity, 36:1-30, 2016. Google Scholar
  44. 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 47th Annual ACM Symposium on Theory of Computing, pages 21-30, 2015. Google Scholar
  45. Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638, 2017. Google Scholar
  46. 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.
  47. Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proc. of the thirtieth annual ACM symposium on Theory of computing, pages 604-613. ACM, 1998. Google Scholar
  48. Stasys Jukna. Boolean function complexity: advances and frontiers, volume 27. Springer Science &Business Media, 2012. Google Scholar
  49. Matti Karppa, Petteri Kaski, and Jukka Kohonen. A faster subquadratic algorithm for finding outlier correlations. In Proc. of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1288-1305. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  50. C.S. Karthik, Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. arXiv preprint arXiv:1711.11029, 2017. Google Scholar
  51. Samir Khuller and Yossi Matias. A simple randomized sieve algorithm for the closest-pair problem. Information and Computation, 118(1):34-37, 1995. Google Scholar
  52. Hartmut Klauck. Rectangle size bounds and threshold covers in communication complexity. In Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on, pages 118-134. IEEE, 2003. Google Scholar
  53. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1272-1287, 2016. Google Scholar
  54. Robert Krauthgamer and Ohad Trabelsi. Conditional lower bounds for all-pairs max-flow. arXiv preprint arXiv:1702.05805, 2017. Google Scholar
  55. Jiří Matoušek. Efficient partition trees. Discrete &Computational Geometry, 8(3):315-334, 1992. Google Scholar
  56. Jiří Matoušek. Range searching with efficient hierarchical cuttings. Discrete &Computational Geometry, 10(2):157-182, 1993. Google Scholar
  57. Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric lshs for inner product search. In Proc. of the 32nd International Conference on Machine Learning, ICML, pages 1926-1934, 2015. Google Scholar
  58. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603-610, 2010. Google Scholar
  59. Mihai Pătraşcu and Ryan Williams. On the possibility of faster sat algorithms. In Proc. of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1065-1075. SIAM, 2010. Google Scholar
  60. Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. Journal of Computer and System Sciences, 33(1):106-123, 1986. Google Scholar
  61. Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In NIPS, volume 3, page 5, 2007. Google Scholar
  62. Parikshit Ram and Alexander G Gray. Maximum inner-product search using cone trees. In Proc. of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 931-939. ACM, 2012. Google Scholar
  63. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proc. of the 45th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 515-524, 2013. Google Scholar
  64. Aviad Rubinstein. Hardness of approximate nearest neighbor search. In STOC, page To appear, 2018. Google Scholar
  65. Anshumali Shrivastava and Ping Li. Asymmetric lsh (alsh) for sublinear time maximum inner product search (mips). In Advances in Neural Information Processing Systems, pages 2321-2329, 2014. Google Scholar
  66. Anshumali Shrivastava and Ping Li. Asymmetric minwise hashing for indexing binary inner products and set containment. In Proc. of the 24th International Conference on World Wide Web, pages 981-991. ACM, 2015. Google Scholar
  67. Christina Teflioudi and Rainer Gemulla. Exact and approximate maximum inner product search with lemp. ACM Transactions on Database Systems (TODS), 42(1):5, 2016. Google Scholar
  68. Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem. Journal of the ACM (JACM), 62(2):13, 2015. Google Scholar
  69. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In To appear in the proceedings of the ICM, 2018. Google Scholar
  70. 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
  71. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 664-673. ACM, 2014. Google Scholar
  72. Ryan Williams. On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1207-1215. SIAM, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.78.
  73. Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1867-1877. SIAM, 2014. Google Scholar
  74. Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721-736, 1982. 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