On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
Received: July 1, 2018
Revised: May 28, 2019
Published: September 23, 2020
Revised: May 28, 2019
Published: September 23, 2020
Keywords: Maximum Inner Product, SETH, hardness of approximation in P, fine-grained complexity, Hopcroft's Problem, Chinese Remainder Theorem
Categories: complexity theory, lower bounds, Maximum Inner Product, SETH, hardness of approximation, fine-grained complexity, Hopcroft's Problem, Chinese Remainder Theorem, CCC, CCC 2018 special issue
ACM Classification: F.1.3
AMS Classification: 68Q17
Abstract: [Plain Text Version]
$
\newcommand{\BQP}{\mathsf{BQP}}
\newcommand{\MA}{\mathsf{MA}}
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\UPP}{\mathsf{UPP}}
\newcommand{\MaxIP}{\textsf{Max-IP}}
\newcommand{\logstar}{\log^{*}}
\newcommand{\Mapprox}[1]{multiplicative $#1$-approximation}
$
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 = \left( d/\log n \right)^{\Omega(1)}$. We also show this is conditionally optimal, as such a $\left(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.