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.