Coin Problem and Circuit Lower Bounds

Tulasi mohan Molli
Aditya Nema
Friday, 21 Jun 2019, 17:15 to 18:15
A-201 (STCS Seminar Room)
The $delta$-coin problem asks if a given function can distinguish between coins which are sampled independently with the probability of heads being $1/2+ \delta$ and those where the probability of heads is 1/2.
Recent works (due to Limaye et al, Chattopadhyay et al) study this problem giving tight lower bounds on the ability of a certain circuit classes to compute the coin problem. This, in turn, leads to better lower bounds for these circuit classes, bounds on ell-1 Fourier degree-1 weight of functions computed by these classes, and new PRGs for these classes.
In this talk, I'll describe the coin problem, show that it cannot be solved by small-size constant depth circuits and improves the lower bounds for these circuit classes.