2026-07-22T11:56:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8330 2024-03-06T10:42:05Z ddc:004 open_access

Pseudorandom Generators for Low Sensitivity Functions Hatami, Pooya Tal, Avishay Pseudorandom Generators Sensitivity Sensitivity Conjecture 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pooya Hatami and Avishay Tal 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.29 urn:nbn:de:0030-drops-83300 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.29 eng https://creativecommons.org/licenses/by/3.0/legalcode