In the world of space-bounded complexity, there is a strain of results showing that space can, somewhat paradoxically, be used for multiple purposes at once. Touchstone results include Barrington’s Theorem and the recent line of work on catalytic computing. We refer to such techniques, in contrast to the usual notion ... more >>>

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22).

In ... more >>>

For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$.

When $p \equiv 3$ mod $4$, it is well known that $f(X) = X^{(p+1)/4}$ computes square ... more >>>