Hard-to-Sample Distributions from Robust Extractors
Anthony Ostuni (UCSD)
Monday, April 27 2026, 2-3pm
Abstract:
We will discuss upcoming work on a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notion of robust extractors, which are extractors that remain sound even when a small number of points violate the min-entropy constraint. Using such objects, we show that for a broad range of sampling models (e.g., low-depth circuits, small-space sources, etc.), every output of the model has distance 1 - o(1) from our target distribution, recovering essentially all previously known hardness results. Our work extends that of Viola (SICOMP '14), who developed an earlier unified framework based on traditional extractors to rule out sampling with very small error.
As a further application of our technique, we leverage a recent extractor construction of Chattopadhyay, Goodman, and Gurumukhani (ITCS '24) to present the first explicit distribution with distance 1 - o(1) from the output of any low-degree F2-polynomial source. We also describe a potential avenue toward proving a similar hardness result for AC0[2] circuits.
Joint w/ Farzan Byramji, Daniel M. Kane, and Jackson Morris