Boolean Functions with Minimal Spectral Sensitivity

Autor:	Prūsis, Krišjānis, Vihrovs, Jevgēnijs
Rok vydání:	2024
Předmět:	Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	In this note we show examples of total Boolean functions that depend on $n$ variables and have spectral sensitivity $\Theta(\sqrt{\log n})$, which is asymptotically minimal.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2412.16088 Zobrazit plný text záznamu View this record from Arxiv