Fall 2018

The Coin Problem and AC^0[parity]

Friday, Sep. 14, 2018 3:00 pm3:30 pm PDT

Add to Calendar


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.