2019/02/06 by Chin Ho Lee, Lee, Chin Ho · 1 citation
Computer Science · Mathematics · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1902.02428
openalex publication_date 2019/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the Fourier spectrum of functions f\colon \0,1\mk → \-1,0,1\ which can be written as a product of k Boolean functions fi on disjoint m-bit inputs. We prove that for every positive integer d, ∑S ⊆ [mk]: |S|=d |fS| = O(m)d . Our upper bound is tight up to a constant factor in the O(⋅). Our proof builds on a new `level-d inequality' that bounds above ∑|S|=d fS2 for any [0,1]-valued function f in terms of its expectation, which may be of independent interest. As a result, we construct pseudorandom generators for such functions with seed length O(m + log(k/ε)), which is optimal up to polynomial factors in log m, loglog k and loglog(1/ε). Our generator in particular works for the well-studied class of combinatorial rectangles, where in addition we allow the bits to be read in any order. Even for this special case, previous generators have an extra O(log(1/ε)) factor in their seed lengths. Using Schur-convexity, we also extend our results to functions fi whose range is [-1,1].