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.