2018/02/07 by Lijie Chen, Chen, Lijie · 2 citations
Computer Science · #Advanced Algebra and Logic #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Rough Sets and Fuzzy Logic #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1802.02325
abstract shortened to meet the constraint
openalex publication_date 2018/02/07 · arxiv created 2018/03/06 · arxiv updated 2018/03/07 · openalex created_date 2021/09/13 · openalex updated_date 2026/07/28
In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets A and B of vectors, and the goal is to find a ∈ A and b ∈ B maximizing inner product a ⋅ b. Max-IP is very basic 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 ℓ2-Furthest Pair (and other important problems in computational geometry) in poly-log-log dimensions in [Williams, SODA 2018]. We have three main results regarding this problem. First, we study the best multiplicative approximation ratio for Boolean Max-IP in sub-quadratic time. We show that, for Max-IP with two sets of n vectors from \0,1\d, there is an n2 - Ω(1) time ( d/log n )Ω(1)-multiplicative-approximating algorithm, and we show this is conditionally optimal, as such a (d/log n)o(1)-approximating algorithm would refute SETH. Second, we achieve a similar characterization for the best additive approximation error to Boolean Max-IP. We show that, for Max-IP with two sets of n vectors from \0,1\d, there is an n2 - Ω(1) time Ω(d)-additive-approximating algorithm, and this is conditionally optimal, as such an o(d)-approximating algorithm would refute SETH [Rubinstein, STOC 2018]. Last, we revisit the hardness of solving Max-IP exactly for vectors with integer entries. We show that, under SETH, for Max-IP with sets of n vectors from ℤd for some d = 2^O(log* n), every exact algorithm requires n2 - o(1) time. With the reduction from [Williams, SODA 2018], it follows that ℓ2-Furthest Pair and Bichromatic ℓ2-Closest Pair in 2^O(log* n) dimensions require n2 - o(1) time.