External Publication
Visit Post

More cool results about the complexity of distributions

cstheory.com May 18, 2026
Source
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. By Manu

Discussion in the ATmosphere

Loading comments...