Talks
Fall 2018

The Coin Problem and AC^0[parity]

Friday, September 14th, 2018 3:00 pm3:30 pm

Add to Calendar

Speaker: 

Srikanth Srinivasan (Indian Institute of Technology 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.