{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreif5p6tglrh6dtl6xlheloze74sek43whdljweqdgaobyieaw3xzlq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmtnsl7ow562"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.26450v1",
  "publishedAt": "2026-05-27T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Haakon Larsen",
    "Tushant Mittal",
    "Silas Richelson",
    "Sourya Roy"
  ],
  "textContent": "**Authors:** Haakon Larsen, Tushant Mittal, Silas Richelson, Sourya Roy\n\nLet $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 points in $T$. 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 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δ}{2}-o(1)$ instead of $\\frac{1+c\\sqrtδ}{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.",
  "title": "Low Soundness Linearity Testing on the Half-Slice"
}