Loading...
Please wait, while we are loading the content...
Similar Documents
On the minimal fourier degree of symmetric boolean functions.
| Content Provider | CiteSeerX |
|---|---|
| Author | Shpilka, Amir Tal, Avishay |
| Abstract | In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function. Specifically, we prove that for every non-linear and symmetric f: {0, 1} k → {0, 1} there exists a set ∅ = S ⊂ [k] such that S = O(Γ(k) + √ k), and ˆ f(S) = 0, where Γ(m) ≤ m 0.525 is the largest gap between consecutive prime numbers in {1,..., m}. As an application we obtain a new analysis of the PAC learning algorithm for symmetric juntas, under the uniform distribution, of Mossel et al. [MOS04]. Namely, we show that the running time of their algorithm is at most n O(k0.525) ·poly(n, 2 k, log(1/δ)) where n is the number of variables, k is the size of the junta (i.e. number of relevant variables) and δ is the error probability. In particular, for k ≥ log(n) 1/(1−0.525) ≈ log(n) 2.1 our analysis matches the lower bound 2 k (up to polynomial factors). Our bound on the degree greatly improves the previous result of Kolountzakis et al. [KLM + 09] who proved that S = O(k / log k). |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Minimal Fourier Degree Symmetric Boolean Function Minimal Degree Relevant Variable Consecutive Prime Number Symmetric Junta Uniform Distribution New Analysis Non-linear Symmetric Boolean Function Polynomial Factor Running Time New Upper Bound Pac Learning Algorithm Previous Result Error Probability Nonzero Fourier Coefficient |
| Content Type | Text |
| Resource Type | Article |
