In this work, we propose a new bounded arithmetic theory, denoted $\mathbf{APX}_1$, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, $\mathbf{APX}_1$ is strictly weaker than previously proposed frameworks, such as the theory $\mathbf{APC}_1$ introduced in the seminal work of Je?ábek ... more >>>

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

A major open problem at the interface of quantum computing and communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they are not. In a seminal work, Razborov (2002) resolved this question for AND-functions of ... more >>>