2026-07-25T15:15:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13272 2024-03-06T10:51:59Z ddc:004 open_access

Randomness Efficient Noise Stability and Generalized Small Bias Sets Moshkovitz, Dana Oh, Justin Zuckerman, David pseudorandomness derandomization epsilon biased sets noise stability We present a randomness efficient version of the linear noise operator T_ρ from boolean function analysis by constructing a sparse linear operator on the space of boolean functions {0,1}ⁿ → {0,1} with similar eigenvalue profile to T_ρ. The linear operator we construct is a direct consequence of a generalization of ε-biased sets to the product distribution 𝒟_p on {0,1}ⁿ where the marginal of each coordinate is p = 1/2-1/2ρ. Such a generalization is a small support distribution that fools linear tests when the input of the test comes from 𝒟_p instead of the uniform distribution. We give an explicit construction of such a distribution that requires log n + O_{p}(log log n + log1/(ε)) bits of uniform randomness to sample from, where the p subscript hides O(log² 1/p) factors. When p and ε are constant, this yields a support size nearly linear in n, whereas previous best known constructions only guarantee a size of poly(n). Furthermore, our construction implies an explicitly constructible "sparse" noisy hypercube graph that is a small set expander. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dana Moshkovitz and Justin Oh and David Zuckerman 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.31 urn:nbn:de:0030-drops-132721 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.31 eng https://creativecommons.org/licenses/by/3.0/legalcode