[theory-seminar] Bonus Theory Seminar on Tuesday (10/23): Srikanth Srinivasan

[Ofir Geri]

Hi all,


On Tuesday (10/23) we will have a bonus theory seminar, where Srikanth Srinivasan (IIT Bombay) will be speaking on constant-depth circuits for the coin problem (abstract below). The talk will be at 4:15 PM in Gates 463A. Please note the non-standard day and time. We will also have theory seminar as usual next Friday (but not tomorrow).


Hope to see you there!

Ofir


On Constant-Depth Circuits for the Coin Problem
Speaker: Srikanth Srinivasan (IIT Bombay)

We come up with explicit functions for which we can prove tight (up to polynomial factors) upper and lower bounds in the AC^0[2] circuit model. In particular, this implies the first Fixed-Depth Size Hierarchy theorem for this model.

The explicit functions are obtained by constructing explicit AC^0[2] circuits for solving the coin problem, which is defined as follows. For a parameter delta, we have to decide whether a given coin has bias (1+delta)/2 or (1-delta)/2.

Our upper bounds are proved by derandomizing a circuit construction of O'Donnell-Wimmer (2007) and Amano (2009) to reduce the number of samples. Our lower bounds follow from a modification of the Razborov-Smolensky polynomial method.

Joint work with Nutan Limaye (IITB CSE), Karteek Sreenivasiah (IITH CSE), Utkarsh Tripathi (IITB Math) and S Venkitesh (IITB Math).

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20181019/64188504/attachment.html>