A data structure for minimum dot product queries
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.