We construct explicit non-malleable affine extractors for every constant entropy rate, with linear output length and exponentially small error, against any fixed number of affine tamperings without fixed points. For every fixed $00$.

Our extractors derandomize the lossless lifting of Efremenko and Itsykson (STOC 2026). For every fixed $0<\xi<1$, this ... more >>>

Beginning with the work of Dinur, Lin, and Vidick (FOCS, 2024), tensor codes with constant product expansion have been foundational to recent advances in quantum locally testable codes (qLTCs) based on cubical complexes. Informally, product expansion says that any low-weight parity check of the tensor code can be written as ... more >>>

We give the first exponential quantum advantage in the general interactive three-party Number-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ quantum ... more >>>