Talks
Fall 2018

The Complexity of Distributions

Friday, September 14th, 2018 11:30 am12:30 pm

Add to Calendar

Speaker: 

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.

AttachmentSize
PDF icon The Complexity of Distributions5.52 MB