In this short expository note, we provide an introduction to a distribution testing (and, more generally, indistinguishability) lower bound method based on moment-matching via polynomials. This method, which underlies several of the tight lower bounds on estimating symmetric properties, had for many years appeared mysterious and near-magical to the ... more >>>

Proving super-linear lower bounds on the size of circuits computing explicit linear functions $A:{\mathbb {F}}^n \to {\mathbb {F}}^n$ is a fundamental long-standing open problem in circuit complexity. We focus on the case where ${\mathbb {F}}$ is a finite field. The circuit can be either a Boolean circuit or an arithmetic ... more >>>

Res($\oplus$) is the simplest fragment of $\text{AC}^0[2]\text{-Frege}$ for which no super-polynomial lower bounds on the size of proofs are known. Bhattacharya and Chattopadhyay [BC25] recently proved lower bounds of the form $\exp(\tilde\Omega(N^{\varepsilon}))$ on the size of Res($\oplus$) proofs whose depth is upper bounded by $O(N^{2 - \varepsilon})$, where $N$ is ... more >>>