Chen, Lijie
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
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 * b. MaxIP is very basic and serves as the base problem in the recent breakthrough of [Abboud et al., FOCS 2017] on hardness of approximation for polynomialtime problems. It is also used (implicitly) in the argument for hardness of exact l_2Furthest Pair (and other important problems in computational geometry) in polyloglog 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 of n vectors from {0,1}^{d}, there is an n^{2  Omega(1)} time (d/log n)^{Omega(1)}multiplicativeapproximating algorithm, and we show this is conditionally optimal, as such a (d/log n)^{o(1)}approximating algorithm would refute SETH. Similar characterization is also achieved for additive approximation for MaxIP.
 2^{O(log^* 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 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 l_2Furthest Pair and Bichromatic l_2Closest Pair in 2^{O(log^* n)} dimensions require n^{2  o(1)} time.
 Connection with NP * UPP Communication Protocols. Last, We establish a connection between conditional lower bounds for exact MaxIP with integer entries and NP * UPP communication protocols for SetDisjointness, parallel to the connection between conditional lower bounds for approximating MaxIP and MA communication protocols for SetDisjointness.
The lower bound in our first result is a direct corollary of the new MA protocol for SetDisjointness 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 Z^{l} where l = 2^{O(log^* d)}, dramatically improving the previous reduction in [Williams, SODA 2018]. The key technical ingredient is a recursive application of Chinese Remainder Theorem.
As a side product, we obtain an MA communication protocol for SetDisjointness with complexity O (sqrt{n log n log log n}), slightly improving the O (sqrt{n} log n) 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 SetDisjointness to prove nearoptimal hardness for approximation to MaxIP with vectors in {1,1}^d. This answers a question from [Abboud et al., FOCS 2017] in the affirmative.
BibTeX  Entry
@InProceedings{chen:LIPIcs:2018:8875,
author = {Lijie Chen},
title = {{On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {14:114:45},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8875},
URN = {urn:nbn:de:0030drops88752},
doi = {10.4230/LIPIcs.CCC.2018.14},
annote = {Keywords: Maximum Inner Product, SETH, Hardness of Approximation in P, FinedGrained Complexity, Hopcroft's Problem, Chinese Remainder Theorem}
}
04.06.2018
Keywords: 

Maximum Inner Product, SETH, Hardness of Approximation in P, FinedGrained Complexity, Hopcroft's Problem, Chinese Remainder Theorem 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

04.06.2018 