2013/04/01 by Amir Shpilka, Avishay Tal, Shpilka, Amir +3 · 4 citations
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #cs.CC #math.CA #math.CO
paper · pdf · doi:10.48550/arxiv.1304.0371
openalex publication_date 2013/04/01 · arxiv created 2013/05/22 · arxiv updated 2013/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is ‖f‖1=∑α|f(α)|). Specifically, we prove the following results for functions f:\0,1\n → \0,1\ with ‖f‖1=A. 1. There is a subspace V of co-dimension at most A2 such that f|V is constant. 2. f can be computed by a parity decision tree of size 2A2n2A. (a parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.) 3. If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth A2 log s. 4. For every 0<ε there is a parity decision tree of depth O(A2 + log(1/ε)) and size 2O(A2) ⋅ min\1/ε2,O(log(1/ε))2A\ that ε-approximates f. Furthermore, this tree can be learned, with probability 1-δ, using \poly(n,exp(A2),1/ε,log(1/δ)) membership queries. All the results above also hold (with a slight change in parameters) to functions f:Zpn→ \0,1\.