Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[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