PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Lijie Chen

arXiv:1802.02325v2cs.CCcs.DS

TL;DR

The paper asks how well Maximum Inner Product can be approximated or solved exactly in truly sub-quadratic time as dimension varies. It combines polynomial-method algorithms with reductions from Orthogonal Vectors and communication-protocol lower bounds. It obtains essentially tight approximation thresholds and proves exact integer Max-IP hardness, with corresponding geometric lower bounds, in 2^{O(log^* n)} dimensions.

  • Problem

    The paper studies the time complexity of approximate and exact Max-IP, a central similarity-search problem whose hardness has implications for computational geometry.

  • Method

    The paper combines polynomial-method and sampling-based algorithms with reductions from OV using improved MA protocols and recursive Chinese Remainder dimensionality reduction.

  • Results

    The paper characterizes sub-quadratic multiplicative approximation at t = (d/log n)^{Ω(1)}, additive approximation at t = Ω(d), and exact integer Max-IP hardness in 2^{O(log^* n)} dimensions.

  • Takeaways & Limitations

    Under SETH or OVC, the approximation thresholds are conditionally tight, and the exact hardness extends to ℓ2-Furthest Pair and Bichromatic ℓ2-Closest Pair.

  • Takeaways & Limitations

    The improved direct reduction still incurs a 2^{O(log^* n)} factor, and its simpler construction requires ℓ ≥ log log n.

Abstract

from arXiv · show

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 \in A$ and $b \in B$ maximizing inner product $a \cdot 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 $\ell_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 $n^{2 - \Omega(1)}$ time $\left( d/\log n \right)^{\Omega(1)}$-multiplicative-approximating algorithm, and we show this is conditionally optimal, as such a $\left(d/\log n\right)^{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 $n^{2 - \Omega(1)}$ time $\Omega(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 $\mathbb{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 $\ell_2$-Furthest Pair and Bichromatic $\ell_2$-Closest Pair in $2^{O(\log^{*} n)}$ dimensions require $n^{2 - o(1)}$ time.

1 Introduction

The paper studies Max-IP as a central similarity-search problem and asks how well it can be approximated, and exactly solved, in truly sub-quadratic time as dimension varies. Under SETH or OVC, it gives essentially tight approximation characterizations and strengthens exact hardness for integer vectors to 2^{O(log^* n)} dimensions.

  • Max-IP asks for the most correlated pair between two vector sets and is a central problem in similarity search with many applications.
  • Prior work established strong multiplicative hardness, but left the dimension dependence and additive approximation complexity unresolved.The earlier lower bound applied only to dimensions d = log^{ω(1)} n and did not address additive approximation.
  • The paper characterizes essentially optimal multiplicative and additive approximations achievable in n^{2−Ω(1)} time under SETH.
  • Exact integer Max-IP remains conditionally hard in 2^{O(log^* n)} dimensions, strengthening the previous ω((log log n)^2)-dimensional lower bound.
  • The results rely on the Orthogonal Vectors conjecture, which is implied by SETH.

Characterizations of Hardness of Approximate Max-IP

The paper gives matching conditional upper and lower bounds for multiplicative and additive approximation of Boolean Max-IP in truly sub-quadratic time. It also transfers the hardness framework to LCS Closest Pair, {−1,1}-Max-IP, All-Pair-Max-IP, and exact integer Max-IP.

  • Multiplicative Approximations for Max-IP: For d = ω(log n), a truly sub-quadratic multiplicative approximation exists exactly when t = (d/log n)^{Ω(1)}, under SETH or OVC.The lower bound rules out t = (d/log n)^{o(1)}; for d = O(log n), exact sub-quadratic algorithms are known.
  • LCS Closest Pair: Assuming SETH or OVC, t-multiplicative LCS Closest Pair requires n^{2−o(1)} time when d = t^{ω(1)}·log^5 n.
  • Additive Approximations for Max-IP: For Boolean Max-IP, a truly sub-quadratic additive approximation is possible exactly at error scale t = Ω(d), under SETH or OVC.The upper bound reduces to d = O(log n) using random-sampling coordinates, while the lower bound rules out smaller errors.
  • All-Pair-Max-IP: The algorithms extend, with adaptations, to All-Pair-Max-IP, which requires an approximation for every vector in the first set.The stated running times include n^{2−Ω(ε_M)} polylog(n) for multiplicative approximation and n^{2−Ω(ε_A^{1/3})} for additive approximation under the supplied parameter conditions.
  • Exact Z-Max-IP: Exact integer Max-IP requires n^{2−o(1)} time even in d = c^{log^* n} dimensions with O(log n)-bit entries, and the same hardness transfers to ℓ2-Furthest Pair and Bichromatic ℓ2-Closest Pair.

Improved Dimensionality Reduction for OV and Hopcroft’s Problem

The paper improves the dimensionality reduction from Orthogonal Vectors to integer Orthogonal Vectors using recursive Chinese Remainder representations. This yields conditional hardness for Hopcroft’s problem and connects exact integer Max-IP hardness to NP·UPP communication protocols.

  • Improved Dimensionality Reduction: A new reduction maps OV in dimension d to ℓ^{O(6^{log^* d}(d/ℓ))} instances of integer OV in dimension ℓ+1.
  • Comparison with [Wil18]: When ℓ = 7^{log^* d}, the improved reduction creates only n^{o(1)} instances, versus n^{ω(1)} under the construction of.
  • Hopcroft’s Problem: The reduction proves that, assuming SETH or OVC, integer OV in c^{log^* n} dimensions with O(log n)-bit entries requires n^{2−o(1)} time.
  • NP·UPP Connection: The same framework yields a super-efficient NP·UPP protocol for Set-Disjointness, including O(o(n), O(log^* n)) computational efficiency when α = 3 log^* n.
  • Conditional Consequence: If an increasing unbounded function f gives the stated NP·UPP protocols for Set-Disjointness, then exact integer Max-IP and the two geometric pair problems require n^{2−o(1)} time in ω(1) dimensions.

Improved MA Protocols for Set-Disjointness

The paper develops improved MA protocols for Set-Disjointness and Inner Product, while explaining the recursive CRT reduction behind its low-dimensional hardness results. The recursion improves instance counts but incurs a 2^{O(log^* n)} factor through repeated growth of coordinate bounds.

  • Improved MA Protocols: The new MA protocol improves on the previous O(√n log n) protocol and approaches the Ω(√n) lower bound of [Kla03].
  • Improved MA Protocols: The protocol also handles Inner Product, whose MA communication complexity is constrained between the prior upper and lower bounds discussed in.
  • CRT Reduction Intuition: Chinese Remainder representations encode blockwise products modulo primes, allowing orthogonality to be recovered from the resulting integer inner products.
  • Reduction Trade-off: The 2^{O(log^* n)} overhead arises because the coordinate-bound exponent at least doubles at each recursion, while the direct construction is limited by the need for ℓ ≥ log log n.
  • Recursive Reduction: Recursive micro-block reductions shrink the number of instances to b^{Θ(b/b_micro)} and, after Θ(log^* n) recursions, yield the improved dimensionality reduction.

2 Preliminaries

The preliminaries establish notation, fast rectangular matrix multiplication tools, number-theoretic encodings, and efficient MA protocols used in later reductions.

  • The paper defines log(x) as base-2 logarithms, ln(x) as natural logarithms, and log*(n) recursively for iterated-logarithm bounds.
  • Fast rectangular matrix multiplication is available in N^2+o(1) time for aspect ratio α > 0.31389 and in N^2·polylog(N) time for α > 0.172.
  • The reduction from OV to integer-vector OV uses the prime number theorem and Chinese remainder representations to encode residue constraints.
  • An (m, r, ℓ, s)-efficient MA protocol specifies Merlin’s advice, shared randomness, Bob’s message, Alice’s decision, and completeness and soundness conditions.
  • Expander graphs reduce the number of random coins required by one communication protocol through a computable function mapping random strings to short output sequences.

3 Hardness of Approximate Max-IP

This section develops subquadratic multiplicative approximations for Boolean Max-IP and proves conditional lower bounds, with extensions to nonnegative inputs and additive approximation.

  • Extensions: The polynomial construction exploits Boolean inputs, where powers of each coordinate collapse, while nonnegative real inputs require a general bound on the number of polynomial terms.The same algorithm extends to R+-Max-IP under a real RAM model.
  • Algorithm: For each block pair, the constructed polynomial satisfies Pr(X,Y)^{1/r} ∈ [OPT(X,Y), OPT(X,Y)·t], providing the multiplicative approximation guarantee.Here OPT(X,Y) is the maximum inner product over the two blocks.
  • Algorithm: The algorithm partitions the input sets into blocks, encodes each block using polynomial evaluations, and reduces all block-pair evaluations to matrix multiplication.The maximum block value is then extracted and its r-th root gives the approximation.
  • Hardness of approximate Max-IP: The lower bound reduces Orthogonal Vectors to multiple Max-IP instances, so a sufficiently fast multiplicative approximation would yield a subquadratic OV algorithm and contradict OVC.The reduction creates n^ε Max-IP instances and preserves a large optimum when an orthogonal pair exists.
  • Hardness of approximate Max-IP: Under SETH or OVC, no n^{2−Ω(1)}-time t-multiplicative approximation exists when t = (d/log n)^{o(1)}.The hardness applies for d = ω(log n) and t ≥ 2.
  • Additive approximation: The section also states conditional hardness for additive approximation: under SETH or OVC, no n^{2−Ω(1)}-time t-additive approximation exists in the stated regime.The supplied theorem statement gives this conclusion for d = ω(log n), with randomized algorithms discussed in the surrounding results.

4 Hardness of Exact Z-Max-IP, Hopcroft’s Problem and More

This section improves the dimensionality reduction from Orthogonal Vectors to integer instances and derives near-quadratic hardness for exact Z-Max-IP and related geometric problems in 2^{O(log^* n)} dimensions.

  • 4.1 Improved Dimensionality Reduction for OV: The core reduction maps {0,1}^{b·ℓ} vectors to Z^ℓ while preserving orthogonality, using recursive Chinese Remainder representations.
  • 4.1 Improved Dimensionality Reduction for OV: The improved reduction converts OV_n,d into ℓ^{O(6log^*d·(d/ℓ))} instances of Z-OV_{n,ℓ+1} with bounded entry bit-length.
  • 4.1 Improved Dimensionality Reduction for OV: After three applications of the reduction, the block length falls to at most log log log b, permitting brute-force construction instead of deeper recursion.
  • 4.4 Hardness for ℓ2-Furthest Pair and Bichromatic ℓ2-Closest Pair: The framework transfers exact hardness from Z-Max-IP to ℓ2-Furthest Pair and Bichromatic ℓ2-Closest Pair through reductions preserving O(log n)-bit entries.
  • 4.3 Hardness for Z-Max-IP: Assuming SETH or OVC, exact Z-Max-IP in c log^* n dimensions requires n^{2-o(1)} time for O(log n)-bit entries.

5 NP · UPP communication protocol and Exact Hardness for Z-Max-IP

This section interprets the OV-to-Z-Max-IP reduction as an NP·UPP protocol for Set-Disjointness and shows that improved such protocols would strengthen exact hardness in constant and slowly growing dimensions.

  • 5.1 NP · UPP Communication Protocol for Set-Disjointness: The reduction yields an NP·UPP communication protocol for Set-Disjointness, paralleling the MA-based connection for approximate Max-IP.
  • 5.2 Exact Hardness for Z-Max-IP: If an increasing unbounded family of efficient NP·UPP protocols for DISJ_n exists, then Z-Max-IP in ω(1) dimensions requires n^{2-o(1)} time under SETH or OVC.
  • 5.1 NP · UPP Communication Protocol for Set-Disjointness: The protocol represents Alice’s and Bob’s behavior as vectors whose inner product equals the protocol’s acceptance probability.
  • 5.2 Exact Hardness for Z-Max-IP: Enumerating Merlin’s advice and solving the resulting constant-dimensional Z-Max-IP instances would produce a subquadratic OV algorithm, contradicting OVC.

6 Improved MA Protocols

This section constructs an improved MA protocol for Set-Disjointness by combining protocols for inner products modulo several primes and checking a claimed integer inner product through random prime selection.

  • 6 Improved MA Protocols: The resulting MA protocol for DISJ_n and IP_n balances advice and interaction costs using a parameter choice proportional to n log n/log log n.
  • 6 Improved MA Protocols: The intermediate IP_p problem asks Alice and Bob to compute X·Y modulo p, while the generalized MA condition verifies the claimed answer with high probability.
  • 6 Improved MA Protocols: The protocol reduces exact inner-product verification to modular protocols over multiple primes, with Merlin supplying advice and a claimed inner product.
  • 6 Improved MA Protocols: When the claimed inner product is wrong, a randomly selected prime is good with probability at least 0.9, yielding rejection probability at least 0.45.
  • 6 Improved MA Protocols: The protocol’s advice length is O(n/T · log n), while Alice–Bob communication is O(T · log log n).

7 Future Works

The paper identifies unresolved questions about improving dimensionality reductions, approximation algorithms, communication protocols, and hardness connections for related problems.

  • Dimensionality reduction: The authors highlight improving the OV dimensionality reduction beyond 2^O(log*n) as the most important open question.They conjecture an ω(1)-dimensional reduction may be possible through a more direct construction.
  • Dimensionality reduction: Combining the polynomial-based and number-theoretic reductions is proposed as a possible route to improving the current construction.The paper describes the approaches as completely different and suggests that combining them may solve the problem.
  • Hardness connections: The paper asks whether direct hardness for Z-Max-IP could bypass OV dimensionality reduction and yield ω(1)-dimensional hardness for geometric problems.The suggested approach starts from the NP · UPP communication-protocol connection and may use known UPP protocols.
  • Problem equivalence: The authors ask whether Z-Max-IP and Z-OV are equivalent, including whether the reduction from Z-Max-IP back to Z-OV can match the efficient forward reduction.The forward reduction from Z-OV to Z-Max-IP increases dimension only quadratically.
  • Algorithms and protocols: Other open questions concern improving the ε-dependence of approximation algorithms, clarifying the relationship between Max-IP and OV runtimes, and strengthening MA protocols for Set-Disjointness.The paper also asks whether an O(√n) MA protocol matching the DISJ lower bound is possible, while noting that new ideas seem necessary.

A A Dimensionality Reduction for Max-IP

This section develops a dimensionality reduction from Boolean Max-IP to integer Max-IP by encoding inner products through a reduced-dimensional representation and test sets.

  • A Dimensionality Reduction for Max-IP: The encoding ψ_b,ℓ maps {0,1}^{b·ℓ} to Z^ℓ and can be computed in polynomial time in b·ℓ.The construction is accompanied by sets V^k that support the equivalence for every possible x and i.
  • A Dimensionality Reduction for Max-IP: The construction reduces Max-IP_n,d to d · ℓ^O(6log*d·(d/ℓ)) instances of Z-Max-IP_n,(ℓ+1)^2.The reduction uses ψ_b,ℓ and enumerates all target inner-product values.
  • A Dimensionality Reduction for Max-IP: The reduction maps Boolean vectors into Z^ℓ while preserving whether each possible inner-product value occurs through membership in corresponding sets V^k.For each k from 0 to d, an original pair has inner product k exactly when the transformed pair’s inner product lies in V^k.
  • A Dimensionality Reduction for Max-IP: The reduction determines the exact Max-IP value by checking the transformed instances for every candidate k.The construction can determine whether some pair has inner product k for every k, and then recover the maximum.

B Nonuniform to Uniform Transformation for Dimensionality Reduction for OV

This section converts nonuniform dimensionality reductions for OV into uniform ones, enabling hardness consequences for integer and geometric problems under stronger reduction families.

  • B Nonuniform to Uniform Transformation for Dimensionality Reduction for OV: The reduction framework encodes orthogonality by requiring x·y=0 exactly when the transformed inner product belongs to a designated set V.A τ-reduction family provides this guarantee for every b and ℓ, while uniformity requires efficient computation of the encoding and set construction.
  • B Nonuniform to Uniform Transformation for Dimensionality Reduction for OV: A τ-reduction family with τ(n)=O(log log log n) can be transformed into a uniform-O(τ)-reduction family.The transformation constructs the small base reduction by brute force and applies the recursive composition lemma three times.
  • B Nonuniform to Uniform Transformation for Dimensionality Reduction for OV: The recursive construction reduces the input block size through smaller reductions, with the original approach requiring log*b recursion levels.The uniform transformation instead applies the reduction only three times after finding a sufficiently small base case.
  • B Nonuniform to Uniform Transformation for Dimensionality Reduction for OV: If an O(1)-reduction family exists, Z-OV, Z-Max-IP, ℓ2-Furthest Pair, and Bichromatic ℓ2-Closest Pair require n^(2−ε) time in some constant dimension.The stated consequence holds for every ε>0 with O(log n)-bit entries.
  • B Nonuniform to Uniform Transformation for Dimensionality Reduction for OV: The hardness consequence follows by obtaining a uniform constant-overhead self-reduction from OV to Z-OV and then applying the existing lower-bound argument.The paper notes that hardness for Z-OV implies the corresponding hardness for the other three problems.

C Hardness of Approximate {−1, 1}-Max-IP via Approximate Polynomial for OR

This section reduces OV to approximate {−1,1}-Max-IP using an approximate polynomial for OR, yielding conditional hardness while noting that the reduction does not provide a full characterization.

  • C Hardness of Approximate {−1,1}-Max-IP via Approximate Polynomial for OR: This approach does not achieve a characterization because setting ε=1/2 yields dimension much larger than log n.Unlike the approximation-hardness reduction discussed elsewhere, it reduces one OV instance to a single {−1,1}-Max-IP instance.
  • C Hardness of Approximate {−1,1}-Max-IP via Approximate Polynomial for OR: The approximate polynomial Pε distinguishes OR(z)=0 from OR(z)≠0, and its discretized form preserves the corresponding inner-product gap.For x·y=0, the transformed polynomial is large; for x·y≠0, its absolute value is small.
  • C Hardness of Approximate {−1,1}-Max-IP via Approximate Polynomial for OR: The construction converts polynomial values into {−1,1} vectors through intermediate {−1,0,1} encodings whose pairwise inner products equal twice the original products.The coordinatewise maps ψx and ψy implement this conversion while preserving the needed sign and magnitude information.
  • C Hardness of Approximate {−1,1}-Max-IP via Approximate Polynomial for OR: An OV instance reduces to {−1,1}-Max-IP so that orthogonal pairs produce a large optimum and nonorthogonal pairs produce a small optimum.The reduction runs in n·poly(d1) time and separates the cases by values proportional to (M/ε).
  • C Hardness of Approximate {−1,1}-Max-IP via Approximate Polynomial for OR: Under SETH or OVC, no n^(2−Ω(1))-time algorithm can distinguish the stated large-OPT and small-OPT cases for subpolynomial approximation factor and dimension β(n)=n^o(1).The theorem specifies an integer threshold T>α and a function β(n)=n^o(1) for any α(n)=n^o(1).

D A Proof of Lemma 3.3

The proof constructs an efficient MA protocol for Set-Disjointness with reduced error, then converts its advice and acceptance behavior into Max-IP instances that distinguish orthogonal from non-orthogonal pairs.

  • MA protocol: The amplified MA protocol uses an expander to generate q correlated random strings, sends q corresponding messages, and lowers the error to ε.Its efficiency is (m/α, log^2 m + O(log ε^-1), poly(α) · log ε^-1, ε).
  • Completeness: If an orthogonal pair exists, some generated Max-IP instance has optimum at least T = c log n · τ^c1.This follows because one advice string makes Alice accept across all relevant random choices.
  • Reduction construction: The reduction creates n^ε Max-IP instances by enumerating all possible advice strings from the MA protocol.With ε = 1/τ, the protocol has 2^{ε·log n} = n^ε possible advice strings, each yielding one instance.
  • Max-IP encoding: For each advice string, vectors encode whether Alice accepts Bob’s messages across random coins, so their inner product counts accepting random choices.The construction concatenates the acceptance vectors for Alice and Bob over all random strings.
  • Soundness: If no orthogonal pair exists, every constructed instance has optimum at most T/τ, creating the gap required by the reduction.The upper bound holds for every pair of vectors and every advice string.
Loading 1802.02325v2…