Abstract:
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.
