Theory of Computing ------------------- Title : On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product Authors : Lijie Chen Volume : 16 Number : 4 Pages : 1-50 URL : https://theoryofcomputing.org/articles/v016a004 Abstract -------- In this paper we study the (Bichromatic) Maximum Inner Product Problem (MaxIP), 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 \cdot b$. MaxIP is a basic question 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 $\ell_2$-Furthest Pair (and other important problems in computational geometry) in poly- loglog 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 $\MaxIP$ in subquadratic time. We show that, for $\MaxIP$ with two sets each consisting of $n$ vectors from $\{0,1\}^{d}$, there is an $n^{2 - \Omega(1)}$-time Multiplicative $t$-approximation algorithm when $t =(d/\log n)^{\Omega(1)}$. We also show this is conditionally optimal, as a $(d/\log n\right)^{o(1)}$-approximation algorithm would refute SETH. Similar characterization is also achieved for additive approximation for $\MaxIP$. * $2^{O(\logstar n)-dimensional Hardness for Exact MaxIP Over The Integers. Second, we revisit the hardness of solving \MaxIP exactly for vectors with integer entries. We show that, under SETH, for $\MaxIP$ with sets of $n$ vectors from $\mathbb{Z}^{d}$ for some $d = 2^{O(\logstar n)}$, every exact algorithm requires $n^{2 - o(1)}$ time. With the reduction from [Williams, SODA 2018], it follows that $\ell_2$-Furthest Pair and Bichromatic $\ell_2$-Closest Pair in dimension $2^{O(\logstar n)}$ require $n^{2 - o(1)}$ time. * Connection with $\NP \cdot \UPP$ Communication Protocols. Last, we establish a connection between conditional lower bounds for exact MaxIP with integer entries and $\NP \cdot \UPP$ communication protocols for Set-Disjointness, parallel to the connection between conditional lower bounds for approximate \MaxIP 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 $\mathbb{Z}^{\ell}$ where $\ell = 2^{O(\logstar d)}$, dramatically improving the previous reduction in [Williams, SODA 2018]. The key technical ingredient is a recursive application of _Chinese Remainder Theorem_. As a by-product we obtain an $\MA$ communication protocol for Set-Disjointness with complexity $O\left(\sqrt{n\log n \log\log n}\right)$, slightly improving the $O\left(\sqrt{n} \log n\right)$ 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 $\MaxIP$ with vectors in $\{-1,1\}^d$. This answers a question from [Abboud et al., FOCS 2017] in the affirmative.