{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreieec3cm7o3sguase5ikyz77zxgfu2qd2xvymextqwhgpeqg4mdqo4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mefmivtepte2"
  },
  "path": "/report/2026/014",
  "publishedAt": "2026-02-09T01:57:31.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "We prove a switching lemma for constant-depth circuits over the alphabet $F_p$ with generalized AND/OR gates, extending Tal's Fourier-analytic approach from the Boolean setting. The key new ingredient is a direct computation of the $L_1$ Fourier mass of AND/OR gates over $F_p$, which yields an exact closed-form expression for the expected high-degree Fourier mass after a random restriction. Combined with a Markov inequality argument, this gives a switching lemma with an explicit, prime-independent structure: $Pr[DT(f|\\rho) \\geq s] \\leq (ep \\cdot qK / ((p-1)s))^s$. As a consequence, we obtain that for any prime $p$, constant-depth circuits of sub-exponential size over $F_p$ cannot compute $1[\\sum_i x_i \\equiv 0 \\pmod{p}]$.",
  "title": "TR26-014 |  A Fourier-Analytic Switching Lemma over F_p and the AC^0 Lower Bound for Generalized Parity | \n\n\tYipin Wang"
}