Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-025 | 16th February 2017 18:12

Pseudorandom Generators for Low-Sensitivity Functions

RSS-Feed




TR17-025
Authors: Pooya Hatami, Avishay Tal
Publication: 16th February 2017 18:27
Downloads: 1966
Keywords: 


Abstract:

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)$.



ISSN 1433-8092 | Imprint