A problem about matrix Assume that $\boldsymbol{v}_{\boldsymbol{1}}, \ldots, \boldsymbol{v}_{\boldsymbol{n}} \in \mathbb{R}^n$ satisfy $\forall i, j \in[n],i \neq j,\left\langle\boldsymbol{v}_{\boldsymbol{i}}, \boldsymbol{v}_{\boldsymbol{j}}\right\rangle=0,\left\|\boldsymbol{v}_{\boldsymbol{i}}\right\|=1$. Let $\mathcal{L}=\left[\boldsymbol{v}_{\boldsymbol{1}}, \ldots, \boldsymbol{v}_{\boldsymbol{n}}\right] \mathbb{Z}^n$.
The problem is the following: for any polynomial $p$ given $\boldsymbol{B}$ (a basis of $\mathcal{L}$ ) and $\boldsymbol{x}_1, \ldots, \boldsymbol{x}_{p(n)}$, each $\boldsymbol{x}_{\boldsymbol{i}}=t_{i 1} \boldsymbol{v}_1+\ldots+t_{i n} \boldsymbol{v}_{\boldsymbol{n}}$, where $t_{i j} \in\{-1,+1\}$ are chosen uniformly at random. The goal is the output $v_1, \ldots, v_n$.
 A: Nice question!
First of all, notice that the most we can hope for is to get $v_i$ up to a permutation and $\pm 1$. Besides these obvious obstructions, the answer is yes.

The $x_i$ are independent and identically distributed, and thus all the information about the $x_i$ comes from taking functions $f : \mathbb{R}^n \to \mathbb{R}$ and computing the expected value of $f(x_i)$ by taking the average over many $x_i$. So, our strategy will be to take certain functions $f$ and compute this average by sampling the $x_i$. Ideally, $f$ would behave nicely with respect to addition because our $x_i$'s are given as sums of many variables. Thus, it makes sense that $f(x) = g(\langle x, v \rangle)$ for some vector $v$ and some function $g : \mathbb{R} \to \mathbb{R}$ which behaves nicely with respect to addition.
The most obvious choice would be a linear function, which for obvious reasons does not give any information.
Another logical choice would be $g(x) = c^x$. This might be doable, but there is a technical problem here that the variance is very large, so it is hard to get a reliable estimate by sampling. Thus, our next choice is polynomials..
Let $g(x) = x^k$. Then, $g(\langle x_i, v \rangle) = \left( \sum_j t_{i1} \langle v_i, v \rangle \right)^k$. Expanding out, we see that $g$ consists of a sum of monomials in $\langle v_i, v \rangle$ with coefficients with the corresponding $t_{i1}$'s. Taking the expected value, we see that the only terms that remain are those where each $t_{i1}$ appears to an even power. In particular, there is no reason to look at $k$ odd.
For $k = 2$ the expected value of $g$ is $\sum_j \langle v_j, v \rangle^2 = \langle v, v \rangle$, so we get no new information. Thus, we need to take $k = 4$.
For $k = 4$ we basically get $\sum_j \langle v_j, v \rangle^4$. Note that both the expected value and the variance are $n^{\Theta (1)}$ and thus with a polynomial number of samples we can compute the expected value to high accuracy. Replacing $v$ with $v + t u$, and taking $5$ values of $t$ we see that we can compute $\sum_j \langle v_j, v \rangle^s \langle v_j, u \rangle^{4 - s}$ for $0 \leq s \leq 4$. In particular taking $s = 1$ we can compute $\sum_j \langle v_j, v \rangle \langle v_j, u \rangle^3 = \langle \sum_j \langle v_j, u \rangle^3 v_j, v \rangle$.
In particular, letting $v$ run over the standard basis vectors we see that we can compute $\sum_j \langle v_j, u \rangle^3 v_j$. Iterating this process $r$ times, we get the vector $\sum_j \langle v_j, u \rangle^{3^r} v_j$. Notice that this vector very quickly becomes proportional to $v_j$, where $j$ is such that $\lvert \langle v_j, u \rangle \rvert$ is largest, and thus we get a good approximation for $v_j$.
Do this $n \log n$ times with different random starting vectors $u$ until (by the coupon collector's problem) we will end up with good guesses for all $v_j$. From this it is easy to find the $v_j$ exactly, because for each $x_i$ we can find out what $t_{ij}$ is by taking the scalar product with our guess for $v_j$ and checking the sign, and then we just get a problem in linear algebra.

As I've mentioned above, each average can be computed to high accuracy with a polynomial number of samples, and we compute this things a polynomial number of times, thus this whole process requires a polynomial number of vectors $x_i$. With a small amount of effort this can be made explicit and I think the constants involved should be quite small.
