{"id":"arxiv/2605.26450","url":"https://arxiv.org/abs/2605.26450","tags":["cs.CC","cs.DM","cs.DS","math.CO"],"score":0,"title":"Low Soundness Linearity Testing on the Half-Slice","domain":"cs.CC","source":"arxiv","authors":["Haakon Larsen","Tushant Mittal","Silas Richelson","Sourya Roy"],"reviews":0,"subject":"cs.CC","summary":"Let $f: T\\to \\{ 0,1 \\}$ be a Boolean function on the Boolean half-slice, $T$, \\ie elements of $\\{0,1\\}^n$ with Hamming weight $n/2$. We show that if $f(x)+f(y)=f(x+y)$ holds with probability $\\frac{1+δ}{2}$ over a uniform pair $(x,y)$ such that $x,y,x+y\\in T$, then $f$ agrees with some linear function on at least $\\frac{1+δ}{2}-o(1)$ fraction of the points in $T$. More generally, we show that if $f$ passes the natural $k$-query BLR test with probability $\\frac{1+δ}{2}$ for any $k\\geq3$, then it must agree with some affine function at $\\frac{1+δ^{\\frac{1}{k-2}}}{2}-o(1)$ fraction of the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-26","reactions":{}}