Fall 2018

The Complexity of Distributions

Friday, Sep. 14, 2018 11:30 am12:30 pm

Add to Calendar


Emanuele Viola (Northeastern University)

I survey the knowledge of the complexity of distributions, with a focus on lower bounds and the many open problems. To mention a concrete result, we give an explicit boolean function whose input-output pairs cannot be sampled by AC^0 circuits noticeably better than picking a uniform input and guessing at random the value of the function.

PDF icon The Complexity of Distributions5.52 MB