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.