Title: Pseudorandom Generators for Low Sensitivity Functions
Speaker: Pooya Hatami, DIMACS
Date: Wednesday, November 30, 2016 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk, we discuss a new PRG (pseudorandom generator) for low sensitivity functions. The sensitivity of a Boolean function f is the maximum, over all inputs x, of the number of sensitive coordinates of x (namely, the number of Hamming neighbors of x with different f-value). We give a PRG with seed-length 2^(sqrt(s)) that fools Boolean functions with sensitivity at most s. Even though assuming the well-known sensitivity conjecture of Nisan and Szegedy would imply a PRG of seed-length poly(s) for functions of sensitivity s, no PRG with seed-length subexponential in s(f) was known before our work.
Our construction is based on a derandomized switching lemma for low sensitivity functions.
Based on joint work with Avishay Tal and Li-Yang Tan.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/