×

On the Fourier spectrum of symmetric Boolean functions. (English) Zbl 1212.42017

Authors’ abstract: We study the following question: What is the smallest \(t\) such that every symmetric boolean function on \(k\) variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least \(1\) and at most \(t\)? We exclude the constant functions for which there is no such \(t\) and the parity functions for which \(t\) has to be \(k\). Let \(\tau (k)\) be the smallest such \(t\). Our main result is that for large \(k, \tau(k)\leq 4k/\log k\). The motivation for our work is to understand the complexity of learning symmetric juntas. A \(k-\)junta is a boolean function of \(n\) variables that depends only on an unknown subset of \(k\) variables. A symmetric \(k-\)junta is a junta that is symmetric in the variables it depends on. Our result implies an algorithm to learn the class of symmetric \(k-\)juntas, in the uniform PAC learning model, in time \(n^{o(k)}\). This improves on a result of E. Mossel, R. O’Donnell and R. A. Servedio [J. Comput. Syst. Sci. 69, No. 3, 421–434 (2004; Zbl 1013.05043)], who show that symmetric \(k-\)juntas can be learned in time \(n^{2k/3}\).

MSC:

42B05 Fourier series and coefficients in several variables
68Q32 Computational learning theory

Citations:

Zbl 1013.05043
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld and N. Xie: Testing {\(\kappa\)}-wise and almost {\(\kappa\)}-wise independence, in: STOC, pages 496–505, 2007.
[2] A. Bernasconi: Mathematical Techniques for the Analysis of Boolean Functions, PhD thesis, Università degli Studi di Pisa, Dipartimento de Informatica, 1998. · Zbl 0917.65118
[3] A. Blum: Relevant examples and relevant features: Thoughts from computational learning theory; in: AAAI Symposium on Relevance, 1994.
[4] A. Blum: Open problems, COLT, 2003.
[5] A. Blum, M. Furst, M. Kearns and R. J. Lipton: Cryptographic primitives based on hard learning problems, in: CRYPTO, pages 278–291, 1993. · Zbl 0870.94021
[6] A. Blum and P. Langley: Selection of relevant features and examples in machine learning, Artificial Intelligence 97 (1997), 245–271. · Zbl 0904.68142 · doi:10.1016/S0004-3702(97)00063-5
[7] N. Bshouty, J. Jackson and C. Tamon: More efficient PAC learning of DNF with membership queries under the uniform distribution, in: Annual Conference on Computational Learning Theory, pages 286–295, 1999. · Zbl 1072.68087
[8] P. Cameron: Combinatorics: topics, techniques, algorithms; Cambridge University Press, 1994. · Zbl 0806.05001
[9] D. Helmbold, R. Sloan and M. Warmuth: Learning integer lattices, SIAM Journal of Computing 21(2) (1992), 240–266. · Zbl 0747.68047 · doi:10.1137/0221019
[10] J. Jackson: An efficient membership-query algorithm for learning dnf with respect to the uniform distribution, Journal of Computer and System Sciences 55 (1997), 414–440. · Zbl 0897.68051 · doi:10.1006/jcss.1997.1533
[11] M. Kolountzakis, E. Markakis and A. Mehta: Learning symmetric juntas in time n o({\(\kappa\)}), in: Proceedings of the conference Interface entre l’analyse harmonique et la theorie des nombres, CIRM, Luminy, 2005.
[12] A. Kumchev: The distribution of prime numbers, manuscript, 2005. · Zbl 1164.11339
[13] N. Linial, Y. Mansour and N. Nisan: Constant depth circuits, fourier transform and learnability; Journal of the ACM 40(3) (1993), 607–620. · Zbl 0781.94006 · doi:10.1145/174130.174138
[14] R. Lipton, E. Markakis, A. Mehta and N. Vishnoi: On the fourier spectrum of symmetric boolean functions with applications to learning symmetric juntas, in: IEEE Conference on Computational Complexity (CCC), pages 112–119, 2005.
[15] Y. Mansour: An o(n loglogn ) learning algorithm for DNF under the uniform distribution, Journal of Computer and System Sciences 50 (1995), 543–550. · Zbl 0837.68100 · doi:10.1006/jcss.1995.1043
[16] E. Mossel, R. O’Donnell and R. Servedio: Learning juntas, in: STOC, pages 206-212, 2003. · Zbl 1192.68393
[17] G. Pólya and G. Szego: Problems and theorems in Analysis, II; Springer, 1976.
[18] T. Siegenthaler: Correlation-immunity of nonlinear combining functions for cryptographic applications, IEEE Transactions on Information Theory 30(5) (1984), 776–780. · Zbl 0554.94010 · doi:10.1109/TIT.1984.1056949
[19] L. Valiant: A theory of the learnable, Communications of the ACM 27(11) (1984), 1134–1142. · Zbl 0587.68077 · doi:10.1145/1968.1972
[20] K. Verbeurgt: Learning DNF under the uniform distribution in quasi-polynomial time, in: Annual Workshop on Computational Learning Theory, pages 314–326, 1990.
[21] K. Verbeurgt: Learning sub-classes of monotone DNF on the uniform distribution, in: Algorithmic Learning Theory, 9th International Conference (Michael M. Richter, Carl H. Smith, Rolf Wiehagen, and Thomas Zeugmann, editors), pages 385–399, 1998. · Zbl 0932.68085
[22] J. von zur Gathen and J. Roche: Polynomials with two values, Combinatorica 17(3) (1997), 345–362. · Zbl 0907.68134 · doi:10.1007/BF01215917
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.