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

We formalize the proof of Reingold's Theorem that SL=L (STOC'05) in the theory of bounded arithmetic VL, which corresponds to ``logspace reasoning''. As a consequence, we get that VL=VSL, where VSL is the theory of bounded arithmetic for ``symmetric-logspace reasoning''. This resolves in the affirmative an old open question from ... more >>>