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

Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hold only for inputs that are $\epsilon$-far from the property being verified, where $\epsilon>0$ is a proximity parameter. In such proof systems, the verifier has oracle access to the ... more >>>