More cool results about the complexity of distributions
Thoughts 2026-05-18
In no particular order,
Byramji, Kane, Morris, and Ostuni proved an almost tight separation for adaptive vs non-adaptive sampling in the word model. Previous papers I blogged about earlier, see this and this prove weaker separations.
Another very cool work is the sampling lower bound for low-degree polynomials by Khodabandeh and Shinkar. They appear to be able to boost a non-trivial sampling lower bound to an exponential one using some type of sunflower result for polynomials.