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

A recent work of Goyal, Harsha, Kumar and Shankar gave nearly linear time algorithms for the list decoding of Folded Reed-Solomon codes (FRS) and univariate multiplicity codes up to list decoding capacity in their natural setting of parameters. A curious aspect of this work was that unlike most list decoding ... more >>>