ECCC-Report TR17-025https://eccc.weizmann.ac.il/report/2017/025Comments and Revisions published for TR17-025en-usThu, 16 Feb 2017 18:27:26 +0200
Paper TR17-025
| Pseudorandom Generators for Low-Sensitivity Functions |
Pooya Hatami,
Avishay Tal
https://eccc.weizmann.ac.il/report/2017/025A 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)$.Thu, 16 Feb 2017 18:27:26 +0200https://eccc.weizmann.ac.il/report/2017/025