How to estimate the input vector norm of inner product with small space cost?

93 Views Asked by At

Given a public vector $A$=$(a_1, a_2, \cdots, a_n) \in \mathbb{Z}^n_q$ and a unknown input vector $B$=$(a_1, a_2, \cdots, a_n)$, which could be sampled from either $\mathbb{Z}^n_2$ or $\mathbb{Z}^n_q$, and their inner product $A \cdot B$=$\sum_{i=1}^{n} a_i\cdot b_i \bmod q$, what's the most efficient way to determine whether $B$ is sampled from $\mathbb{Z}^n_2$ or $\mathbb{Z}^n_q$ in terms of space cost? To put it another way, how could one determine the infinity norm of $B$ using the least space? A straightforward way would be to simply publish $B$ itself, however, that would obviously take a linear space cost. Does there exist an algorithm that estimates the norm of $B$ correctly with non-negligible probability using sublinear space?