Biased Linearity Testing in the 1% Regime

Abstract

We study linearity testing over the $p$-biased hypercube $(\{0,1{\}}^n,\hat{I}{¼}_p^{\otimes n})$ in the 1% regime. For a distribution $\hat{I}½$ supported over $\{x\in \{0,1{\}}^k:{\sum }_{i=1}^k{x}_i=0\text{ (mod 2)}\}$, with marginal distribution $\hat{I}{¼}_p$ in each coordinate, the corresponding $k$-query linearity test $\text{Lin}(\hat{I}½)$ proceeds as follows: Given query access to a function $f:\{0,1{\}}^n\to \{-1,1\}$, sample $(x_1,\dots ,x_k)\sim \hat{I}{½}^{\otimes n}$, query $f$ on $x_1,\dots ,x_k$, and accept if and only if ${\prod }_{i\in [k]}f(x_i)=1$. Building on the work of Bhangale, Khot, and Minzer (STOC '23), we show, for $0<p\le \frac{1}{2}$, that if $k\ge 1+\frac{1}{p}$, then there exists a distribution $\hat{I}½$ such that the test $\text{Lin}(\hat{I}½)$ works in the 1% regime; that is, any function $f:\{0,1{\}}^n\to \{-1,1\}$ passing the test $\text{Lin}(\hat{I}½)$ with probability $\ge \frac{1}{2}+\hat{I}\mu$, for some constant $\hat{I}\mu >0$, satisfies ${\mathrm{Pr}}_{x\sim \hat{I}{¼}_p^{\otimes n}}[f(x)=g(x)]\ge \frac{1}{2}+\hat{I}´$, for some linear function $g$, and a constant $\hat{I}´=\hat{I}´(\hat{I}\mu )>0$. Conversely, we show that if $k<1+\frac{1}{p}$, then no such test $\text{Lin}(\hat{I}½)$ works in the 1% regime. Our key observation is that the linearity test $\text{Lin}(\hat{I}½)$ works if and only if the distribution $\hat{I}½$ satisfies a certain pairwise independence property.