Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR17-025 | 16th February 2017 18:12

Pseudorandom Generators for Low-Sensitivity Functions

TR17-025
Authors: Pooya Hatami, Avishay Tal
Publication: 16th February 2017 18:27
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)$.