A data structure for minimum dot product queries Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of the following format: given $x \in \mathbb{R}^n$ output $\min_i \langle x, v_i \rangle$. Is it possible to go beyond the trivial $O(nm)$ query time? For example if $n = 2$, then it is immediate to get $O(\log^2 m)$.

The only thing I can come up with is the following. It is an immediate consequence of Johnson-Lindenstrauss lemma that for every $\varepsilon &gt; 0$ and a distribution $\mathcal{D}$ on $\mathbb{R}^n$ there is a linear mapping $f \colon \mathbb{R}^n \to \mathbb{R}^{O(\log m)}$ (which can be evaluated in $O(n \log m)$ time) such that $\mathrm{Pr}_{x \sim \mathcal{D}}\left[\forall i \quad \langle x, v_i \rangle - \varepsilon (\|x\| + \|v_i\|)^2 \leq \langle f(x), f(v_i)\rangle \leq \langle x, v_i \rangle + \varepsilon (\|x\| + \|v_i\|)^2 \right] \geq 1 - \varepsilon$. So, in time $O((n + m) \log m)$ we can compute something that is in some sense close to $\min_i \langle x, v_i \rangle$ for most $x$'s (at least if the norms $\|x\|$ and $\|v_i\|$ are small).

UPD The abovementioned bound can be somewhat sharpened to the query time $O(n + m)$ if we use locality-sensitive hashing. More precisely, we choose $k := O(\frac{1}{\varepsilon^2})$ independent Gaussian vectors $r_1, r_2, \ldots, r_k$. Then we map $\mathbb{R}^n$ to $\{0,1\}^k$ as follows: $v \mapsto (\langle r_1, v \rangle \geq 0, \langle r_2, v \rangle \geq 0, \ldots, \langle r_k, v \rangle \geq 0)$. Then we can estimate the angle between two vectors within an additive error $\varepsilon$ by computing $\ell_1$-distance in the image of this mapping. Thus, we can estimate dot products within an additive error $\varepsilon \|x\| \|v_i\|$ in $O(\frac{1}{\varepsilon^2})$ time.
Consider the special case where you just want to determine if your query vector is orthogonal to some vector in your preprocessed collection. (That is, you want to determine if $\min_i \langle x, v_i \rangle = 0$, where the vectors under discussion have non-negative coefficients.) This case is already very interesting.

Suppose you can answer queries in $n^{O(1)} m^{1-\delta}$ time for some $\delta &gt; 0$, with $m^{O(1)} n^{O(1)}$ preprocessing (the polynomial's degrees should not depend on $m$ or $n$ or $\delta$). 

In the paper "A new algorithm for optimal 2-constraint satisfaction and its implications", I observed that such a data structure would actually allow you to solve CNF-SAT in $2^{\alpha v}$ time for some $\alpha &lt; 1$, where $v$ is the number of variables. This would refute the "Strong Exponential Time Hypothesis" that k-SAT requires essentially $2^n$ time for unbounded $k$.

To see why, suppose the preprocessing time is bounded by $(nm)^c$. Consider a CNF formula $F$ with $v$ variables and $n$ clauses. We split the set of variables into two parts $P_1$ and $P_2$ of size $v(1-1/(2c))$ and $v/(2c)$, respectively. List all possible assignments to the variables in the parts (getting $2^{v(1-1/(2c))}$ and $2^{v/(2c)}$ assignments, respectively). Associate each of these partial assignments $A_i$ with an $n$-bit vector $w_i$ where $w_i[j]=1$ iff the $j$th clause of $F$ is not satisfied by $A_i$. So we have two lists of exponentially many bit vectors.

Notice that $F$ is satisfiable iff there is a vector $w_1$ from an assignment on $P_1$ and a vector $w_2$ from an assignment on $P_2$ such that $\langle w_1, w_2 \rangle = 0$.

Now let $m=2^{v/(2c)}$, and preprocess the assumed data structure with all vectors from part $P_2$. This takes $n2^{v/2}$ time, by assumption. Run the query algorithm on all vectors from assignments on part $P_1$. By assumption this takes $2^{v(1-1/(2c))} \cdot n^{O(1)} m^{1-\delta} = n^{O(1)} 2^{v - \delta v/(2c)}$. Let $\alpha = 1 - \delta/(2c)$.

Perhaps it is possible to get efficient preprocessing and $n^{O(1)} m^{1-1/(\log \log m)}$ query time with existing techniques. The best known CNF-SAT algorithms don't rule it out. (They get something like $2^{n-n/\log n}$.) But to compute $\min_i \langle x, v_i\rangle$ is slightly stronger -- in this setup, it would be like solving MAX CNF-SAT.