Coin Problem and Circuit Lower Bounds

Speaker: 

Time: 

Friday, 21 June 2019, 17:15 to 18:15

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

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.