MATH Seminar

Title: Fooling bounded depth circuits
Seminar: Combinatorics
Speaker: Domingos Dellamonica of The University of Sao Paulo
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2016-11-14 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: Abstract: We will present a very nice breakthrough result of Mark Braverman which establishes that polynomially sized bounded depth circuits are "fooled" by t-independent distributions (for polylogarithmic t). In simpler words, for any circuit C of size m in this class, given any distribution D of n-bit strings (elements in {0, 1}^n) such that the bits are t-wise independent (t = polylog(m)), the distribution of C(D) is practically identical to that of C(U), where U is the uniform distribution. This result was recently applied by E. Chattopadhyay and D. Zuckerman (2016) to essentially derandomize the Binomial Random Graph G(N, 1/2). As a corollary they now hold the record for the best bounds on Ramsey Graphs explicitly constructed by an algorithm.