  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 \cdot 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
$\ell_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.
  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 $\left( d/\log
n \right)^{\Omega(1)}$-multiplicative-approximating algorithm, and we show this
is conditionally optimal, as such a $\left(d/\log
n\right)^{o(1)}$-approximating algorithm would refute SETH.
  Second, we achieve a similar characterization for the best additive
approximation error to Boolean Max-IP. We show that, for Max-IP with two sets
of $n$ vectors from $\{0,1\}^{d}$, there is an $n^{2 - \Omega(1)}$ time
$\Omega(d)$-additive-approximating algorithm, and this is conditionally
optimal, as such an $o(d)$-approximating algorithm would refute SETH
[Rubinstein, STOC 2018].
  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 $\mathbb{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 $\ell_2$-Furthest Pair and Bichromatic $\ell_2$-Closest Pair in
$2^{O(\log^{*} n)}$ dimensions require $n^{2 - o(1)}$ time.
