{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:43:50Z","timestamp":1759063430388},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,5,1]],"date-time":"2009-05-01T00:00:00Z","timestamp":1241136000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2009,5]]},"DOI":"10.1007\/s00493-009-2310-z","type":"journal-article","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T05:50:52Z","timestamp":1246513852000},"page":"363-387","source":"Crossref","is-referenced-by-count":13,"title":["On the Fourier spectrum of symmetric Boolean functions"],"prefix":"10.1007","volume":"29","author":[{"given":"Mihail N.","family":"Kolountzakis","sequence":"first","affiliation":[]},{"given":"Richard J.","family":"Lipton","sequence":"additional","affiliation":[]},{"given":"Evangelos","family":"Markakis","sequence":"additional","affiliation":[]},{"given":"Aranyak","family":"Mehta","sequence":"additional","affiliation":[]},{"given":"Nisheeth K.","family":"Vishnoi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,7,3]]},"reference":[{"key":"2310_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld and N. Xie: Testing \u03ba-wise and almost \u03ba-wise independence, in: STOC, pages 496\u2013505, 2007.","DOI":"10.1145\/1250790.1250863"},{"key":"2310_CR2","unstructured":"A. Bernasconi: Mathematical Techniques for the Analysis of Boolean Functions, PhD thesis, Universit\u00e0 degli Studi di Pisa, Dipartimento de Informatica, 1998."},{"key":"2310_CR3","unstructured":"A. Blum: Relevant examples and relevant features: Thoughts from computational learning theory; in: AAAI Symposium on Relevance, 1994."},{"key":"2310_CR4","unstructured":"A. Blum: Open problems, COLT, 2003."},{"key":"2310_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, M. Furst, M. Kearns and R. J. Lipton: Cryptographic primitives based on hard learning problems, in: CRYPTO, pages 278\u2013291, 1993.","DOI":"10.1007\/3-540-48329-2_24"},{"key":"2310_CR6","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0004-3702(97)00063-5","volume":"97","author":"A. Blum","year":"1997","unstructured":"A. Blum and P. Langley: Selection of relevant features and examples in machine learning, Artificial Intelligence 97 (1997), 245\u2013271.","journal-title":"Artificial Intelligence"},{"key":"2310_CR7","doi-asserted-by":"crossref","unstructured":"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\u2013295, 1999.","DOI":"10.1145\/307400.307472"},{"key":"2310_CR8","doi-asserted-by":"crossref","unstructured":"P. Cameron: Combinatorics: topics, techniques, algorithms; Cambridge University Press, 1994.","DOI":"10.1017\/CBO9780511803888"},{"issue":"2","key":"2310_CR9","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1137\/0221019","volume":"21","author":"D. Helmbold","year":"1992","unstructured":"D. Helmbold, R. Sloan and M. Warmuth: Learning integer lattices, SIAM Journal of Computing 21(2) (1992), 240\u2013266.","journal-title":"SIAM Journal of Computing"},{"key":"2310_CR10","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J. Jackson","year":"1997","unstructured":"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\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"2310_CR11","unstructured":"M. Kolountzakis, E. Markakis and A. Mehta: Learning symmetric juntas in time n o(\u03ba), in: Proceedings of the conference Interface entre l\u2019analyse harmonique et la theorie des nombres, CIRM, Luminy, 2005."},{"key":"2310_CR12","unstructured":"A. Kumchev: The distribution of prime numbers, manuscript, 2005."},{"issue":"3","key":"2310_CR13","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"N. Linial, Y. Mansour and N. Nisan: Constant depth circuits, fourier transform and learnability; Journal of the ACM 40(3) (1993), 607\u2013620.","journal-title":"Journal of the ACM"},{"key":"2310_CR14","doi-asserted-by":"crossref","unstructured":"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\u2013119, 2005.","DOI":"10.1109\/CCC.2005.19"},{"key":"2310_CR15","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1006\/jcss.1995.1043","volume":"50","author":"Y. Mansour","year":"1995","unstructured":"Y. Mansour: An o(n loglogn ) learning algorithm for DNF under the uniform distribution, Journal of Computer and System Sciences 50 (1995), 543\u2013550.","journal-title":"Journal of Computer and System Sciences"},{"key":"2310_CR16","doi-asserted-by":"crossref","unstructured":"E. Mossel, R. O\u2019Donnell and R. Servedio: Learning juntas, in: STOC, pages 206-212, 2003.","DOI":"10.1145\/780542.780574"},{"key":"2310_CR17","doi-asserted-by":"crossref","unstructured":"G. P\u00f3lya and G. Szeg\u0151: Problems and theorems in Analysis, II; Springer, 1976.","DOI":"10.1007\/978-1-4757-6292-1"},{"issue":"5","key":"2310_CR18","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1109\/TIT.1984.1056949","volume":"30","author":"T. Siegenthaler","year":"1984","unstructured":"T. Siegenthaler: Correlation-immunity of nonlinear combining functions for cryptographic applications, IEEE Transactions on Information Theory 30(5) (1984), 776\u2013780.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"11","key":"2310_CR19","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"L. Valiant: A theory of the learnable, Communications of the ACM 27(11) (1984), 1134\u20131142.","journal-title":"Communications of the ACM"},{"key":"2310_CR20","doi-asserted-by":"crossref","unstructured":"K. Verbeurgt: Learning DNF under the uniform distribution in quasi-polynomial time, in: Annual Workshop on Computational Learning Theory, pages 314\u2013326, 1990.","DOI":"10.1016\/B978-1-55860-146-8.50027-8"},{"key":"2310_CR21","doi-asserted-by":"crossref","unstructured":"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\u2013399, 1998.","DOI":"10.1007\/3-540-49730-7_27"},{"issue":"3","key":"2310_CR22","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01215917","volume":"17","author":"J. Gathen von zur","year":"1997","unstructured":"J. von zur Gathen and J. Roche: Polynomials with two values, Combinatorica 17(3) (1997), 345\u2013362.","journal-title":"Combinatorica"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-009-2310-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-009-2310-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-009-2310-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T21:32:46Z","timestamp":1559079166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-009-2310-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["2310"],"URL":"https:\/\/doi.org\/10.1007\/s00493-009-2310-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5]]}}}