文章基本信息
- 标题：On the Structure of Boolean Functions with Small Spectral Norm
- 本地全文：下载
- 作者：Amir Shpilka ; Ben lee Volk ; Avishay Tal 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2013
- 卷号：2013
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is f1=f() ). Specifically, we prove the following results for functions f:01n01 with f1=A .
1. There is a subspace V of co-dimension at most A2 such that fV 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 A2logs.
4. For every 0 there is a parity decision tree of depth O(A2+log(1)) and size 2O(A2)min12O(log(1))2A that -approximates f. Furthermore, this tree can be learned, with probability 1−, using poly(nexp(A2)1log(1)) membership queries.
All the results above also hold (with a slight change in parameters) to functions f:Zpn01 .
