Search Mailing List Archives
[theory-seminar] Bonus Theory Seminar on Tuesday (10/23): Srikanth Srinivasan
ofirgeri at stanford.edu
Thu Oct 18 20:12:01 PDT 2018
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!
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 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 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...
More information about the theory-seminar