Name
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 initiate the study of pseudorandom generators fooling low-sensitivity functions as an intermediate step towards settling the sensitivity conjecture. We construct a pseudorandom generator with seed-length 2^{O(s^{1/2})} log(n) that fools Boolean functions on n variables with maximal sensitivity at most s. Prior to our work, the (implicitly) best pseudorandom generators for this class of functions required seed-length 2^{O(s)} log(n). |
Year | Venue | Field |
|---|---|---|
2018 | ITCS | Boolean function,Discrete mathematics,Hamming code,Pseudorandom generator,Conjecture,Mathematics,Pseudorandom number generator |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pooya Hatami | 1 | 94 | 14.40 |
| Avishay Tal | 2 | 58 | 11.83 |