2026-07-24T17:25:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18135 2024-03-06T11:01:07Z ddc:004 open_access

Searching for Regularity in Bounded Functions Iyer, Siddharth Whitmeyer, Michael regularity bounded function Boolean function Fourier analysis Given a function f on F₂ⁿ, we study the following problem. What is the largest affine subspace 𝒰 such that when restricted to 𝒰, all the non-trivial Fourier coefficients of f are very small? For the natural class of bounded Fourier degree d functions f: F₂ⁿ → [-1,1], we show that there exists an affine subspace of dimension at least Ω(n^{1/d!} k^{-2}), wherein all of f’s nontrivial Fourier coefficients become smaller than 2^{-k}. To complement this result, we show the existence of degree d functions with coefficients larger than 2^{-d log n} when restricted to any affine subspace of dimension larger than Ω(d n^{1/(d-1)}). In addition, we give explicit examples of functions with analogous but weaker properties. Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of F₂ⁿ that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siddharth Iyer and Michael Whitmeyer 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.83 urn:nbn:de:0030-drops-181351 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.83 eng https://creativecommons.org/licenses/by/4.0/legalcode