ECCC-Report TR13-049https://eccc.weizmann.ac.il/report/2013/049Comments and Revisions published for TR13-049en-usWed, 22 May 2013 20:30:13 +0300
Revision 1
| On the Structure of Boolean Functions with Small Spectral Norm |
Amir Shpilka,
Avishay Tal,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2013/049#revision1In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.
1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.
2. $f$ can be computed by a parity decision tree of size $2^{A^2} n^{2A}$. (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 $A^2\log s$.
4. For every $0<\epsilon$ there is a parity decision tree of depth $O(A^2 + \log(1/\epsilon))$ and size $2^{O(A^2)} \cdot \min\{ 1/\epsilon^2,O(\log(1/\epsilon))^{2A}\}$ that $\epsilon$-approximates $f$. Furthermore, this tree can be learned, with probability $1-\delta$, using poly$(n,\exp(A^2),1/\epsilon,\log(1/\delta))$ membership queries.
All the results above also hold (with a slight change in parameters) to functions $f:Z_p^n\to \{0,1\}$.Wed, 22 May 2013 20:30:13 +0300https://eccc.weizmann.ac.il/report/2013/049#revision1
Paper TR13-049
| On the Structure of Boolean Functions with Small Spectral Norm |
Amir Shpilka,
Ben Lee Volk,
Avishay Tal
https://eccc.weizmann.ac.il/report/2013/049In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.
1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.
2. $f$ can be computed by a parity decision tree of size $n^{A^2}$. (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 $A^2\log s$.
4. For every $0<\epsilon$ there is a parity decision tree of depth $A^3\log(1/\epsilon)$ that $\epsilon$-approximates $f$. Furthermore, this tree can be learned, with probability $1-\delta$, using poly$(n,A,1/\epsilon,\log(1/\delta))$ membership queries.
All the results above also hold (with a slight change in parameters) to functions $f:Z_p^n\to \{0,1\}$.Mon, 01 Apr 2013 15:15:29 +0300https://eccc.weizmann.ac.il/report/2013/049