Volume 16 (2020) Article 4 pp. 1-50
CCC 2018 Special Issue

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

by Lijie Chen

Received: July 1, 2018
Revised: May 28, 2019
Published: September 23, 2020

$ \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.

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.

DOI: 10.4086/toc.2020.v016a004

© 2020 Lijie Chen
Licensed under a Creative Commons Attribution License (CC-BY)