On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
Speaker
Lijie Chen
Host
Akshay Degwekar, Pritish Kamath and Govind Ramnarayan
MIT CSAIL
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 between a and 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.
1. 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. 2^{O(log* n)}-dimensional Hardness for Exact Max-IP Over The Integers. Last, 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.
3. Connection with NP dot UPP Communication Protocols. Last, We establish a connection between conditional lower bounds for exact Max-IP with integer entries and NP dot 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 bounds in our first and second results make use of a new MA protocol for Set-Disjointness introduced in [Rubinstein, 2017]. Our algorithms utilize the polynomial method and simple random sampling. Our third 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 using Chinese Remainder Theorem, where l = 2^{O(log* d)}, dramatically improving the previous reduction in [Williams, SODA 2018].
As a side product, we obtain an MA communication protocol for Set-Disjointness with complexity O(sqrt{nlog n loglog 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 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.
1. 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. 2^{O(log* n)}-dimensional Hardness for Exact Max-IP Over The Integers. Last, 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.
3. Connection with NP dot UPP Communication Protocols. Last, We establish a connection between conditional lower bounds for exact Max-IP with integer entries and NP dot 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 bounds in our first and second results make use of a new MA protocol for Set-Disjointness introduced in [Rubinstein, 2017]. Our algorithms utilize the polynomial method and simple random sampling. Our third 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 using Chinese Remainder Theorem, where l = 2^{O(log* d)}, dramatically improving the previous reduction in [Williams, SODA 2018].
As a side product, we obtain an MA communication protocol for Set-Disjointness with complexity O(sqrt{nlog n loglog 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 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.