Consider $n$ arbitrary (but fixed) unit-norm vectors $\mathbf{x}_1,\ldots,\mathbf{x}_n$ in, say, $\mathbb{R}^d$. Let $\beta>0$ be fixed. For $\mathbf{y}\in\mathbb{R}^d$, define the binary quantities $b_i = \mathbf{1}(|\langle \mathbf{x}_i,\mathbf{y}\rangle| < \beta)\in\{0,1\}$, where $\mathbf{1}(\cdot)$ is the indicator function, and $|\langle \cdot,\cdot\rangle|$ is the absolute value of the inner product. Suppose that for any given $\mathbf{y}$ and $i\in\{1,\ldots,n\}$, calculating $b_i$ takes $O(1)$ time. Can calculating all $b_1,\ldots,b_n$ be accomplished in $o(n)$ time for any $\mathbf{y}$?
Asked
Active
Viewed 41 times
0
-
I don't quite understand -- it seems to me that we cannot even output all $b_1,\dots,b_n$ in $o(n)$ time, so then we could not compute them in that time. Am I missing something? – usul Jul 02 '13 at 00:26
-
@usul No, you are not missing anything. I shall admit that the question is not precise enough and I need to think about a proper way to fix it perhaps. What I had in mind was something like this: A "similar" problem. You are given $n$ arbitrary names, $x_0 = Jack$, $x_1 = Mike$, etc. For a given name $y$, define $b_i = \mathbf{1}(x_i,lexicographically,comes,before y)$. Say calculating $b_i$ takes $O(1)$ time. We can calculate all $b_i$ using binary search in $O(\log n)$ time. I guess what I want to assume that is that the only source of time consumption is the calculation of $b_i$ itself. – Lord Soth Jul 02 '13 at 02:21
-
Hmmm, it's tricky because it's still not clear/formal/precise what you mean to calculate "all" $b_i$. In your example, I don't think really can calculate all of them in $\log n$ time, not in the sense of "figure out what each is and write it down." – usul Jul 02 '13 at 19:23