Integer multiplication when one integer is fixed $n$ is a parameter in the problem.
For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.
Problem: Given $n$ what is the complexity of multiplication function $f_n(x)=a_nx$ where $x\in\{0,1,\dots,2^n-1\}$?
One is allowed to pre-process integers $a_n$ as appropriate.
Upper Bound: We already have $n^{1+\epsilon}$ complexity algorithms by $\mathsf{FFT}$ and Karatsuba.
The query here is whether $\epsilon=0$ by anything cleverer?
Conjecture: $\exists c&gt;0,n_0&gt;0$ such that at every $n\in\mathbb Z_{&gt;n_0}$ the number of constants $a_n$ where $\epsilon=0$ is supported is $&gt;2^{cn}$.
While it won't always be the most efficient algorithm, this question has a very close relationship with addition chains; any algorithm for computing $A$ quickly by addition chains translates into an algorithm for computing $f(B) = AB$ by repeated addition (each addition, of course, being an $O(n)$ operation).  Contrariwise, a quick algorithm for computing $AB$ for any $B$ leads to a quick algorithm for computing $A$, but of course this algorithm doesn't necessarily have to have the form of an addition chain; still, that seems like an excellent place to start.  Have a look at http://en.wikipedia.org/wiki/Addition_chain or check out vol. 2 of The Art Of Computer Programming for more details.