pith. sign in

arxiv: 2605.26450 · v1 · pith:KT5BZHSUnew · submitted 2026-05-26 · 💻 cs.CC · cs.DM· cs.DS· math.CO

Low Soundness Linearity Testing on the Half-Slice

Haakon Larsen , Tushant Mittal , Silas Richelson , Sourya Roy This is my paper

Pith reviewed 2026-06-29 15:01 UTC · model grok-4.3

classification 💻 cs.CC cs.DMcs.DSmath.CO
keywords linearity testinghalf-sliceBoolean functionsdense model theoremKrawtchouk polynomialsBLR testproperty testing
0
0 comments X

The pith

If a function on the half-slice passes the 3-query BLR test with probability (1+δ)/2 then it agrees with an affine function on (1+δ)/2 - o(1) fraction of points.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that linearity testing on the Boolean half-slice works with the same parameters as on the full hypercube even when the test passes with only a small advantage δ. A sympathetic reader would care because this domain arises in coding theory and constraint satisfaction, and earlier slice results required either four or more queries or weaker agreement guarantees. The authors prove the claim by building a dense model theorem that transfers linearity correlations from the slice to the hypercube, using bounds on Krawtchouk polynomials. Once the transfer is made, the classical BLR analysis applies directly. The same Krawtchouk bounds also yield a simpler k-query test for k at least 5 that works over larger alphabets without any dense-model step.

Core claim

If f passes the natural k-query BLR test with probability (1+δ)/2 for any k≥3, then f agrees with some affine function at (1 + δ^{1/(k-2)})/2 - o(1) fraction of the points in T. For the 3-query case this yields agreement (1+δ)/2 - o(1). The only prior low-soundness result on the slice required k≥4 and obtained a weaker constant factor in front of the square-root term.

What carries the argument

A dense model theorem that embeds the half-slice into the full hypercube while preserving linearity-test correlations, proved via bounds on Krawtchouk polynomials.

If this is right

  • The 3-query test achieves the optimal linear dependence on δ, matching the hypercube.
  • For k=4 the agreement is (1 + sqrt(δ))/2 - o(1), removing the small constant factor present in prior work.
  • A simplified k-query test exists for k≥5 that avoids the dense-model step entirely.
  • The simplified test extends directly to the slice over the q-ary hypercube.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same Krawtchouk-based transfer may apply to testing other local properties such as dictatorship on the slice.
  • The o(1) term could be replaced by an explicit function of n and δ with a more quantitative analysis of the polynomial bounds.
  • The approach suggests a route to low-soundness testing for other constant-weight domains that lack a direct hypercube embedding.

Load-bearing premise

The Krawtchouk polynomial bounds invoked to prove the dense model theorem are sufficiently strong for the relevant range of parameters and n used in the reduction from the slice to the full hypercube.

What would settle it

An explicit family of functions on the half-slice that passes the 3-query test with probability (1+δ)/2 yet agrees with every affine function on at most (1+δ)/2 - ε fraction of points for some fixed ε>0 and arbitrarily large n.

read the original abstract

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+\delta}{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+\delta}{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+\delta}{2}$ for any $k\geq3$, then it must agree with some affine function at $\frac{1+\delta^{\frac{1}{k-2}}}{2}-o(1)$ fraction of the points in $T$. The only other known linearity test for the slice in the low soundness regime (i.e., when $\delta$ 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 for $k=3$ queries, instead of requiring $k\geq4$; secondly, our result is sharper, e.g., when $k=4$, we are able to conclude an agreement of $\frac{1+\sqrt{\delta}}{2}-o(1)$ instead of $\frac{1+c\sqrt{\delta}}{2}$ for $c\approx.0035$. In particular, our result matches (up to the $o(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 simple $k$-query test ($k\geq 5$) that avoids any use of the dense model machinery. This simplified test naturally extends to the slice over the $q$-ary hypercube, giving the first such result over larger alphabets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper claims that Boolean functions f on the half-slice T (weight-n/2 vectors in {0,1}^n) that pass the natural k-query BLR test with probability (1+δ)/2 must agree with an affine function on at least (1 + δ^{1/(k-2)})/2 - o(1) fraction of T, for any k≥3. This improves on Kalai-Lifshitz-Minzer-Ziegler (FOCS'24) by supporting k=3 and sharper constants (e.g., √δ for k=4). The proof introduces a dense model theorem based on Krawtchouk polynomial bounds to reduce to the hypercube case; a simpler k-query test (k≥5) avoiding dense models is also given and extended to q-ary alphabets.

Significance. If the Krawtchouk bounds deliver the stated error terms uniformly for small δ, the result supplies the first 3-query low-soundness linearity test on the slice and matches the classical hypercube exponent up to o(1), which is a meaningful advance for property testing on restricted domains. The dense-model technique and the simplified test for larger k/q-ary cases are additional technical contributions that could apply more broadly.

major comments (1)
  1. [§3 (dense model theorem)] The dense model theorem (whose statement appears after the main theorem in the introduction and is proved in §3): the claimed agreement exponent 1/(k-2) requires that the total-variation or correlation error produced by the Krawtchouk-based model is o(δ^{1/(k-2)}) uniformly as δ→0 and n→∞. The manuscript invokes external Krawtchouk bounds but does not supply an explicit error analysis or lemma showing that the additive losses remain smaller than δ^{1/(k-2)} in the low-δ regime; without this, the improvement over Kalai et al. is not yet verified.
minor comments (2)
  1. [Theorem statements (abstract and §1)] The o(1) terms in the main theorem statements should be accompanied by a brief remark on their dependence on n (or a reference to the precise rate in the proof).
  2. [§2 (preliminaries)] Notation for the half-slice T and the test distribution (uniform pairs x,y,x+y∈T) is introduced without an explicit equation number; adding one would improve readability when the reduction to the hypercube is discussed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting the need for explicit error analysis in the dense model theorem. We address the comment below and will incorporate the requested verification in the revision.

read point-by-point responses

  1. Referee: [§3 (dense model theorem)] The dense model theorem (whose statement appears after the main theorem in the introduction and is proved in §3): the claimed agreement exponent 1/(k-2) requires that the total-variation or correlation error produced by the Krawtchouk-based model is o(δ^{1/(k-2)}) uniformly as δ→0 and n→∞. The manuscript invokes external Krawtchouk bounds but does not supply an explicit error analysis or lemma showing that the additive losses remain smaller than δ^{1/(k-2)} in the low-δ regime; without this, the improvement over Kalai et al. is not yet verified.

    Authors: We agree that an explicit lemma is needed to confirm the error terms. In the revised manuscript we will insert a new lemma in §3 that derives the total-variation (or correlation) distance of the Krawtchouk-based dense model directly from the cited polynomial bounds. Using the known uniform decay rates of the relevant Krawtchouk coefficients for small δ and large n, the lemma will establish that the additive loss is o(δ^{1/(k-2)}) uniformly in the low-δ regime, thereby justifying the claimed exponent and the improvement over prior work. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses external Krawtchouk bounds and hypercube reduction

full rationale

The paper derives the claimed agreement fraction (1 + δ^{1/(k-2)})/2 - o(1) via a new dense model theorem that invokes standard external bounds on Krawtchouk polynomials to reduce the half-slice BLR test to the known hypercube case. No equation or definition in the provided text reduces the output agreement probability to a quantity fitted from or defined by the input test acceptance probability itself. The cited prior work (Kalai et al. FOCS'24) is by different authors and serves only as a baseline for comparison, not a load-bearing self-citation. The argument is therefore self-contained against external mathematical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard mathematical facts about Krawtchouk polynomials and the existence of a dense model; no free parameters are fitted to data and no new entities are postulated.

axioms (1)
  • standard math Standard bounds and orthogonality properties of Krawtchouk polynomials hold for the relevant degree and weight parameters on the hypercube.
    Invoked to establish the dense model theorem that reduces the slice test to the full-cube case.

pith-pipeline@v0.9.1-grok · 5975 in / 1427 out tokens · 43374 ms · 2026-06-29T15:01:54.482494+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Algebraic Combinatorics

    Eiichi Bannai, Etsuko Bannai, Tatsuro Ito, and Rie Tanaka. Algebraic Combinatorics . Number volume 5 in De Gruyter Series in Discrete Mathematics and Applications. De Gruyter, 2021. https://doi.org/10.1515/9783110630251 doi:10.1515/9783110630251

    work page doi:10.1515/9783110630251 2021

  2. [2]

    Kiwi, and Madhu Sudan

    Mihir Bellare, Don Coppersmith, Johan H stad, Marcos A. Kiwi, and Madhu Sudan. Linearity testing in characteristic two. IEEE Trans. Inf. Theory , 42(6):1781--1795, 1996. https://doi.org/10.1109/18.556674 doi:10.1109/18.556674

    work page doi:10.1109/18.556674 1996

  3. [3]

    Self-testing/correcting with applications to numerical problems

    Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the 22nd ACM Symposium on Theory of Computing , 1990. https://doi.org/10.1145/100216.100225 doi:10.1145/100216.100225

    work page doi:10.1145/100216.100225 1990

  4. [4]

    Direct Sum Testing

    Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. Direct Sum Testing . SIAM Journal on Computing , 46(4):1336--1369, 2017. https://doi.org/10.1137/16M1061655 doi:10.1137/16M1061655

    work page doi:10.1137/16m1061655 2017

  5. [5]

    Uniformity norms, their weaker versions, and applications

    Pandelis Dodos and Vassilis Kanellopoulos. Uniformity norms, their weaker versions, and applications. Acta Arithmetica , 2016. https://doi.org/10.4064/aa210728-27-2 doi:10.4064/aa210728-27-2

    work page doi:10.4064/aa210728-27-2 2016

  6. [6]

    Boolean constant degree functions on the slice are juntas

    Yuval Filmus and Ferdinand Ihringer. Boolean constant degree functions on the slice are juntas. Discrete Mathematics , 342(12), 2019. https://doi.org/10.1016/j.disc.2019.111614 doi:10.1016/j.disc.2019.111614

    work page doi:10.1016/j.disc.2019.111614 2019

  7. [7]

    An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube

    Yuval Filmus. An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube . The Electronic Journal of Combinatorics , 2016. https://doi.org/10.37236/4567 doi:10.37236/4567

    work page doi:10.37236/4567 2016

  8. [8]

    Friedgut-- K alai-- N aor theorem for slices of the B oolean cube

    Yuval Filmus. Friedgut-- K alai-- N aor theorem for slices of the B oolean cube. Chicago Journal of Theoretical Computer Science , 14:1--17, 2016. https://doi.org/10.4086/cjtcs.2016.014 doi:10.4086/cjtcs.2016.014

    work page doi:10.4086/cjtcs.2016.014 2016

  9. [9]

    Invariance Principle on the Slice

    Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer. Invariance Principle on the Slice . In Proceedings of the 31st IEEE Conference on Computational Complexity , 2016. https://doi.org/10.4230/LIPIcs.CCC.2016.15 doi:10.4230/LIPIcs.CCC.2016.15

    work page doi:10.4230/lipics.ccc.2016.15 2016

  10. [10]

    Local decoding and testing for homomorphisms

    Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Local decoding and testing for homomorphisms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 2006. https://doi.org/10.1007/11830924_35 doi:10.1007/11830924_35

    work page doi:10.1007/11830924_35 2006

  11. [11]

    A Fourier-Analytic Approach to Reed-Muller Decoding

    Parikshit Gopalan. A Fourier-Analytic Approach to Reed-Muller Decoding . IEEE Trans. Inf. Theory , 59(11):7747--7760, 2013. https://doi.org/10.1109/TIT.2013.2274007 doi:10.1109/TIT.2013.2274007

    work page doi:10.1109/tit.2013.2274007 2013

  12. [12]

    M. Kiwi. Algebraic testing and weight distributions of codes. Theoretical Computer Science , 299(1):81--106, 2003. https://doi.org/10.1016/S0304-3975(02)00816-2 doi:10.1016/S0304-3975(02)00816-2

    work page doi:10.1016/s0304-3975(02)00816-2 2003

  13. [13]

    1178–1192.doi:10.1109/FOCS61266.2024.00077.url:https://doi.org/10

    Gil Kalai, Noam Lifshitz, Dor Minzer, and Tamar Ziegler. A Dense Model Theorem for the Boolean Slice . In Proceedings of the 65th IEEE Symposium on Foundations of Computer Science , 2024. https://arxiv.org/abs/2402.05217 arXiv:2402.05217 , https://doi.org/10.1109/FOCS61266.2024.00056 doi:10.1109/FOCS61266.2024.00056

    work page doi:10.1109/focs61266.2024.00056 2024

  14. [14]

    A General Framework for Low Soundness Homomorphism Testing

    Tushant Mittal and Sourya Roy. A General Framework for Low Soundness Homomorphism Testing . In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , 2026. https://arxiv.org/abs/2509.05871 arXiv:2509.05871 , https://doi.org/10.4230/LIPIcs.ITCS.2026.103 doi:10.4230/LIPIcs.ITCS.2026.103

    work page doi:10.4230/lipics.itcs.2026.103 2026

  15. [15]

    On the degree of boolean functions as real polynomials

    Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity , 4(4), 1994. https://doi.org/10.1007/bf01263419 doi:10.1007/bf01263419

    work page doi:10.1007/bf01263419 1994

  16. [16]

    Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Dense Subsets of Pseudorandom Sets . In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science , 2008. https://doi.org/10.1109/FOCS.2008.38 doi:10.1109/FOCS.2008.38

    work page doi:10.1109/focs.2008.38 2008