Search Mailing List Archives
[theory-seminar] Bonus Theory Seminar on Tuesday (10/23): Srikanth Srinivasan
Ofir Geri
ofirgeri at stanford.edu
Tue Oct 23 13:15:06 PDT 2018
Reminder: Srikanth Srinivasan will be speaking at theory seminar today at 4:15pm.
________________________________
From: theory-seminar <theory-seminar-bounces at lists.stanford.edu> on behalf of Ofir Geri <ofirgeri at stanford.edu>
Sent: Thursday, October 18, 2018 8:12:01 PM
To: thseminar at cs.stanford.edu
Subject: [theory-seminar] Bonus Theory Seminar on Tuesday (10/23): Srikanth Srinivasan
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/20181023/fe75b18f/attachment.html>
More information about the theory-seminar
mailing list