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

arXiv: https://arxiv.org/abs/1802.02325 · HTML: https://mlsanity.com/paper/1802.02325/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2018.

## Built on by (most cited first, 12 of 12)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Subquadratic Algorithms and Hardness for Attention with Any Temperature](https://mlsanity.com/paper/2505.14840/) (2025)
- [On Complexity of 1-Center in Various Metrics](https://mlsanity.com/paper/2112.03222/) (2021)
- [Can You Solve Closest String Faster than Exhaustive Search?](https://mlsanity.com/paper/2305.16878/) (2023)

## Abstract (arXiv)

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,1d, there is an n2 - 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 nright)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,1d, there is an n2 - 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 mathbbZd 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.