Anindya De
Univeristy of California, Berkeley,
Date: Friday, September 2nd, 2011
Time: 5:15 PM
Venue: CS101.
The talk deals with the following seemingly different problems :
Using (as a black box) a long line of work on affine extractors, we show that it is possible to extract approximately k^2/n bits from any distribution sampled by a NC0 circuit which has min-entropy k as long as k>> n^{2/3} with inverse exponential error. Next, using this result, we construct an an explicit function f : {0,1}^n -> {0,1} such that it is not possible to sample (U_n, f(U_n)) up to inverse exponential error (over random) by NC0 circuits. The previous best result by Viola (FOCS 2010) could only show a function f : {0,1}^n -> {0,1} such that it is not possible to sample (U_n, f(U_n)) up to inverse logarithmic error.
This is a joint work with Thomas Watson (Berkeley) and is to appear in RANDOM 2011.