Name
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; $\not 0 \ne S \subset [k]$ such that S = O (Γ( k )+√ k , and $\hat f(S) \ne 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. [10].Our bound on the degree is a significant improvement over the previous result of Kolountzakis et al. [8] who proved that S = O ( k =log k ).We also show a connection between lower-bounding the degree of non-constant functions that take values in {0,1,2} and the question that we study here. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00493-014-2875-z | Combinatorica |
Keywords | DocType | Volume |
new analysis,kolountzakis etal,non-linear symmetric boolean function,symmetric junta,log k,forevery non-linear,pac learningalgorithm,consecutive prime number,number ofvariables,minimal degree,minimal fourier degree,symmetric boolean functions,algorithm design and analysis,correlation,algorithm design,boolean function,boolean functions,fourier transform,spectrum,symmetric functions,symmetric function,mathematical model,fourier transforms,polynomials | Conference | 34 |
Issue | ISSN | ISBN |
3 | 1093-0159 E-ISBN : 978-0-7695-4411-3 | 978-0-7695-4411-3 |
Citations | PageRank | References |
6 | 0.56 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amir Shpilka | 1 | 1095 | 64.27 |
| Avishay Tal | 2 | 58 | 11.83 |