One of the most fundamental problems in the field of hypothesis testing is the identity testing problem: whether samples from some unknown distribution $\mathcal{G}$ are actually from some explicit distribution $\mathcal{D}$. It is known that when the distribution $\mathcal{D}$ has support $[N]$, the optimal sample complexity for the identity testing ... more >>>

We study the Kaufman--Oppenheim coset complexes (STOC 2018, Eur. J. Comb. 2023), which have an elementary and strongly explicit description. Answering an open question of Kaufman, Oppenheim, and Weinberger (STOC 2025), we show that they support sparse direct-product testers in the low soundness regime. Our proof relies on the HDX ... more >>>

Optimal small-bias sets sit at the crossroads of coding theory and pseudorandomness. Reaching optimal parameters would, in particular, meet the long-standing goal of matching the Gilbert-Varshamov bound for binary codes in the high-distance regime. In a breakthrough, Ta-Shma (STOC 2017) constructed near-optimal small-bias sets via the Rozenman-Wigderson expander-walk framework, using ... more >>>