Abstract: We study linearity testing over the \(p\)-biased hypercube \((\{0,1\}^n, \mu_p^{\otimes n})\) in the 1\% regime. For a distribution \(\nu\) supported over \(\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0 \textnormal{ (mod 2)} \}\), with marginal distribution \(\mu_p\) in each coordinate, the corresponding \(k\)-query linearity test \(\textnormal{Lin}(\nu)\) proceeds as follows: Given query access to a function \(f:\{0,1\}^n\to \{-1,1\}\), sample \((x_1,\dots,x_k)\sim \nu^{\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\leq \frac{1}{2}\), that if \(k \geq 1+\frac{1}{p}\), then there exists a distribution \(\nu\) such that the test \(\textnormal{Lin}(\nu)\) works in the 1\% regime; that is, any function \(f:\{0,1\}^n\to \{-1,1\}\) passing the test \(\textnormal{Lin}(\nu)\) with probability \(\geq \frac{1}{2}+\epsilon\), for some constant \(\epsilon>0\), satisfies \(\Pr_{x\sim \mu_p^{\otimes n}}[f(x)=g(x)] \geq \frac{1}{2}+\delta\), for some linear function \(g\), and a constant \(\delta = \delta(\epsilon)>0\).

Conversely, we show that if \(k < 1+\frac{1}{p}\), then no such test \(\textnormal{Lin}(\nu)\) works in the 1\% regime. Our key observation is that the linearity test \(\textnormal{Lin}(\nu)\) works if and only if the distribution \(\nu\) satisfies a certain pairwise independence property.

Biased Linearity Testing in the 1% Regime