Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FOURIER ANALYSIS OVER FINITE FIELDS:
Reports tagged with Fourier analysis over finite fields:
TR26-014 | 9th February 2026
Yipin Wang

A Fourier-Analytic Switching Lemma over F_p and the AC^0 Lower Bound for Generalized Parity

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 ... more >>>




ISSN 1433-8092 | Imprint