2025/02/04 by Khot, Subhash, Mittal, Kunal · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.01900
We study linearity testing over the p-biased hypercube (\0,1\n, μp⊗ n) in the 1% regime. For a distribution ν supported over \x∈ \0,1\k:∑i=1k xi=0 (mod 2) \, with marginal distribution μp in each coordinate, the corresponding k-query linearity test Lin(ν) proceeds as follows: Given query access to a function f:\0,1\n→ \-1,1\, sample (x1,…,xk)∼ ν⊗ n, query f on x1,…,xk, and accept if and only if ∏i∈ [k]f(xi)=1. Building on the work of Bhangale, Khot, and Minzer (STOC '23), we show, for 0 < p ≤ (1)/(2), that if k ≥ 1 + (1)/(p), then there exists a distribution ν such that the test Lin(ν) works in the 1% regime; that is, any function f:\0,1\n→ \-1,1\ passing the test Lin(ν) with probability ≥ (1)/(2)+ε, for some constant ε> 0, satisfies Prx∼ μp⊗ n[f(x)=g(x)] ≥ (1)/(2)+δ, for some linear function g, and a constant δ= δ(ε)>0. Conversely, we show that if k < 1+(1)/(p), then no such test Lin(ν) works in the 1% regime. Our key observation is that the linearity test Lin(ν) works if and only if the distribution ν satisfies a certain pairwise independence property.