Let $A\in \mathbb{R}^{n\times n}$ and $u$ and $v$ be independent random $\{-1,1\}^n$-vectors. (i.e., each coordinate of $u$ is $1$ with prob. $1/2$ and $-1$ with prob. 1/2 and the coordinates of $u$ are independent with each other)


**Question.** Is there a tail bound for $\Pr\{u^T A v > t\}$? 


I am hoping something like $\Pr\{|u^T A v| > t\} \leq e^{-c\_n ||A||\_F^2}$, where $||A||\_F$ is the Frobenius norm of $A$ and $c\_n < 1$ is some constant dependent on $n$. Is this possible?


I saw that there had been work to bound the quadratic form $\Pr\{u^T A u > t\}$ but I cannot find anything regarding the bilinear form $u^T Av$.



bilinear form tail bound
You can write the bilinear form as a quadratic form, by letting x = (u,v) and rewrite the matrix A.


