Bounded-norm strengthening of the bipartite inner-product compression theorem

Let $a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\in\mathbb{R}^n$ have Euclidean norm at most $1$, let $0<\varepsilon<1$, and set

$$t=\left\lfloor C\frac{\log(2+\varepsilon^2 n)}{\varepsilon^2}\right\rfloor,$$

where $C$ is the absolute constant from Theorem

. Suppose there are vectors $x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n\in\mathbb{R}^t$ satisfying $|\langle x_i,y_j\rangle-\langle a_i,b_j\rangle|\leq\varepsilon$ for all $i,j$. **The bounded-norm strengthening.** Under the assumptions of Theorem

, the conclusion holds together with the further requirement that

$$\|x_i\|\leq O(1)\quad\text{and}\quad\|y_i\|\leq O(1)$$

for all $1\leq i\leq n$. This conjecture strengthens the bipartite version of approximate inner-product compression by requiring uniformly bounded norms for the compressed vectors; it remains open, although the paper establishes two supporting results.