TR17-025 Authors: Pooya Hatami, Avishay Tal

Publication: 16th February 2017 18:27

Downloads: 349

Keywords:

A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at most $s$. Prior to our work, the best pseudorandom generators for this class of functions required seed-length $2^{O(s)} \cdot \log(n)$.