We revisit the framework of interactive proofs for distribution testing, first introduced by Chiesa and Gur (ITCS 2018), which has recently experienced a surge in interest, accompanied by notable progress (e.g., Herman and Rothblum, STOC 2022, FOCS 2023; Herman, RANDOM~2024).
In this model, a data-poor verifier determines whether a ... more >>>

The space complexity of deterministic streaming algorithms for approximating the length of the longest increasing subsequence (LIS) in a string of length $n$ has been known to be $\tilde{\Theta}(\sqrt{n})$ for almost two decades. In contrast, the space complexity of this problem for randomized streaming algorithms remains one of the few ... more >>>

In this paper we ask how much expansion one can retain with almost no edges beyond connectivity. Concretely, for graphs of average degree $2+\varepsilon$, what is the “Ramanujan bound’’—how does spectral expansion scale with $\varepsilon$? We compare five ultra–sparse graph models—including the configuration model, subdivision of regular expanders, and the ... more >>>