License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.14
URN: urn:nbn:de:0030-drops-88752
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8875/
Chen, Lijie
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
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.
BibTeX - Entry
@InProceedings{chen:LIPIcs:2018:8875,
author = {Lijie Chen},
title = {{On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {14:1--14:45},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-069-9},
ISSN = {1868-8969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8875},
URN = {urn:nbn:de:0030-drops-88752},
doi = {10.4230/LIPIcs.CCC.2018.14},
annote = {Keywords: Maximum Inner Product, SETH, Hardness of Approximation in P, Fined-Grained Complexity, Hopcroft's Problem, Chinese Remainder Theorem}
}
|
Keywords: |
|
Maximum Inner Product, SETH, Hardness of Approximation in P, Fined-Grained Complexity, Hopcroft's Problem, Chinese Remainder Theorem |
|
Collection: |
|
33rd Computational Complexity Conference (CCC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
