DIMACS Theory of Computing Seminar

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


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/