Logo image
Back
Low Soundness Linearity Testing on the Half-Slice
Preprint   Open access

Low Soundness Linearity Testing on the Half-Slice

Haakon Larsen, Tushant Mittal, Silas Richelson and Sourya Roy
ArXiv.org
Cornell University
05/26/2026
DOI: 10.48550/arxiv.2605.26450
url
https://doi.org/10.48550/arxiv.2605.26450View
Preprint (Author's original) This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

Letf: T→ { 0,1 }be a Boolean function on the Boolean half-slice,T , ıe elements of{0,1}ⁿwith Hamming weightn/2 . We show that iff(x)+f(y)=f(x+y)holds with probability((1+δ)/2)over a uniform pair(x,y)such thatx,y,x+y∈ T , thenfagrees with some linear function on at least((1+δ)/2)-o(1)fraction of the points inT . More generally, we show that iffpasses the naturalk -query BLR test with probability((1+δ)/2)for anyk≥3 , then it must agree with some affine function at((1+δ^((1/(k-2))))/2)-o(1)fraction of the points inT . The only other known linearity test for the slice in the low soundness regime (i.e., whenδcan be arbitrarily small) was given by Kalai, Lifshitz, Minzer, and Ziegler [FOCS'24]. Our result improves upon this result in two significant ways: firstly, it works fork=3queries, instead of requiringk≥4 ; secondly, our result is sharper, e.g., whenk=4 , we are able to conclude an agreement of((1+\sqrtδ)/2)-o(1)instead of((1+c\sqrtδ)/2)forc≈.0035 . In particular, our result matches (up to theo(1)term) the conclusion one obtains over the full hypercube via the classical BLR analysis. Our main technical contribution is a new dense model theorem using bounds on Krawtchouk polynomials. Using these Krawtchouk polynomial bounds, we also obtain a simplek -query test ( k≥ 5 ) that avoids any use of the dense model machinery. This simplified test naturally extends to the slice over theq -ary hypercube, giving the first such result over larger alphabets.
 Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics Mathematics - Combinatorics

Details

Metrics

1 Record Views
Logo image