# Recover boolean vector from dot products

Question:

I want to determine a boolean vector $$b \in \{0,1\}^n$$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product of $$b$$ with a real-valued vector $$v \in \mathbb{R}^n$$ of my choosing. I.e., access to $$b$$ is available through evaluation of the map $$v \mapsto b^T v.$$ How can I recover all of the entries of $$b$$ using as few of these dot products as possible? (maybe even just 1 dot product?)

Below I detail a couple ideas I had which might work in theory, but which don't work in practice (I think). For concreteness, one may assume that $$n \approx 1 \text{ million}$$, and arithmetic is done in double precision floating point format. This question arose as a subproblem in a machine learning application.

Idea 1:

One idea I had is to use a vector with fast growing entries. Say, for example, $$n=9$$. Then we could use the vector $$v=\begin{bmatrix}1 & 10 & 100 & 1000 & \dots\end{bmatrix}^T.$$ One could then read off $$b$$ as the digits of $$b^T v$$. The problem with this solution is that the numbers grow so fast, that in finite precision computer arithmetic it will not work for large $$n$$.

Idea 2:

Another idea I had was to use a vector with entries that are algebraically independent. Then determining $$b$$ from $$b^Tv$$ is a subset sum problem.

For example, if $$n=3$$ and $$v = \begin{bmatrix}\pi & e & 1\end{bmatrix}^T,$$ then $$b^T v$$ will take on one of a finite number of possibilities, $$b^T v \in \{\pi,~e,~1,~\pi+e,~\pi+1,~e+1,~\pi+e+1\}.$$ We can determine which of these is the case, thereby determining $$b$$.

But this seems quite combinatorial, and therefore unfeasible for large $$n$$.

• "$b^T v \in \{\pi,~e,~1,~\pi+e,~\pi+1,~e+1,~\pi+e+1\}$". 0 is missing. – Apass.Jack Jul 25 at 6:49

1. Let $$v=[2^0, 2^1, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$$. Obtain $$b^Tv$$, which will determine the first 64 entries of $$b$$.
2. Let $$v=[0, 0, 0, \cdots, (64 \text { zeros}), 1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$$. Obtain $$b^Tv$$, which will determine the next 64 entries of $$b$$.
3. Let $$v=[0, 0, 0, \cdots, (128 \text { zeros}), 1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$$. Obtain $$b^Tv$$, which will determine the next 128 entries of $$b$$.
4. And so on, until we have determined all entries of $$b$$. There may be less than 64 positive numbers in $$v$$ in the last round.
The above scheme is the best possible if the number of effective bits in $$b^Tv$$ is 64 and we have no prior knowledge about $$v$$ except the number of its entries. This can be seen easily from information theory, as each query against the black box can provide at most 64 bits of information.