{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T12:18:13Z","timestamp":1769084293962,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2007,9,2]],"date-time":"2007-09-02T00:00:00Z","timestamp":1188691200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2007,10,10]]},"DOI":"10.1007\/s11128-007-0061-6","type":"journal-article","created":{"date-parts":[[2007,9,4]],"date-time":"2007-09-04T22:50:58Z","timestamp":1188946258000},"page":"323-348","source":"Crossref","is-referenced-by-count":48,"title":["Quantum Algorithms for Learning and Testing Juntas"],"prefix":"10.1007","volume":"6","author":[{"given":"Alp","family":"At\u0131c\u0131","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,2]]},"reference":[{"key":"61_CR1","unstructured":"Ambainis A., Iwama K., Kawachi A., Masuda H., Putra R.H., and Yamashita S., in Proceedings of STACS 2004, pp. 93\u2013104 (2003)."},{"key":"61_CR2","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s11128-005-0001-2","volume":"4","author":"A. At\u0131c\u0131","year":"2005","unstructured":"At\u0131c\u0131 A., Servedio R.A. (2005). Quantum Information Process. 4, 355\u2013386","journal-title":"Quantum Information Process."},{"key":"61_CR3","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1137\/S0097539795293123","volume":"28","author":"N.H. Bshouty","year":"1999","unstructured":"Bshouty N.H., Jackson J.C. (1999). SIAM J. Comp. 28, 1136\u20131153","journal-title":"SIAM J. Comp."},{"key":"61_CR4","doi-asserted-by":"crossref","unstructured":"J. Castro, in Proceedings of 17th ALT, pp. 78\u201392 (2006).","DOI":"10.1007\/11894841_10"},{"key":"61_CR5","unstructured":"M. Hunziker, Meyer D.A., J. Park, J. Pommersheim, and M. Rothstein, The Geometry of Quantum Learning, arXiv:quant-ph\/0309059; Quantum Information Processing (to appear)."},{"key":"61_CR6","unstructured":"K. Iwama, A. Kawachi, R. Raymond, and S. Yamashita, Robust Quantum Algorithms for Oracle Identification, arXiv:quant-ph\/0411204 (2005)."},{"key":"61_CR7","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1137\/S0097539704412910","volume":"33","author":"R.A. Servedio","year":"2004","unstructured":"Servedio R.A., Gortler S.J. (2004). SIAM J. Comp. 33, 1067\u20131092","journal-title":"SIAM J. Comp."},{"key":"61_CR8","unstructured":"H. Buhrman, L. Fortnow, I. Newman, and H. R\u00f6hrig, in Proceedings of 14th SODA, pp. 480\u2013488 (2003)."},{"key":"61_CR9","unstructured":"K. Friedl, F. Magniez, M. Santha, and P. Sen, in Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, pp. 419\u2013428."},{"key":"61_CR10","doi-asserted-by":"crossref","unstructured":"F. Magniez and A. Nayak, in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, pp. 1312\u20131324 (2005).","DOI":"10.1007\/11523468_106"},{"key":"61_CR11","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J.C. Jackson","year":"1997","unstructured":"Jackson J.C. (1997). J. Comput. Syst. Sci. 55, 414\u2013440","journal-title":"J. Comput. Syst. Sci."},{"key":"61_CR12","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant L.G. (1984). Commun. Assoc. Comp. Machinery 27, 1134\u20131142","journal-title":"Commun. Assoc. Comp. Machinery"},{"key":"61_CR13","doi-asserted-by":"crossref","unstructured":"J. Arpe and R. Reischuk, in Proceedings of the 14th International Conference on Algorithmic Learning Theory, pp. 99\u2013113 (2003).","DOI":"10.1007\/978-3-540-39624-6_10"},{"key":"61_CR14","doi-asserted-by":"crossref","unstructured":"J. Arpe and R. Reischuk, in Proceedings of the 3rd International Conference on Theory and Applications of Models of Computation, pp. 387\u2013398 (2006).","DOI":"10.1007\/11750321_37"},{"key":"61_CR15","doi-asserted-by":"crossref","unstructured":"A. Blum, in Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop, pp. 731\u2013733 (2003).","DOI":"10.1007\/978-3-540-45167-9_54"},{"key":"61_CR16","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.ipl.2004.01.023","volume":"90","author":"H. Chockler","year":"2004","unstructured":"Chockler H., Gutfreund D. (2004). Information Process. Lett. 90, 301\u2013305","journal-title":"Information Process. Lett."},{"key":"61_CR17","unstructured":"E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pp. 103\u2013112 (2002)."},{"key":"61_CR18","unstructured":"R. Lipton, E. Markakis, A. Mehta, and N. Vishnoi, in Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 112\u2013119 (2005)."},{"key":"61_CR19","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/j.jcss.2004.04.002","volume":"69","author":"E. Mossel","year":"2004","unstructured":"Mossel E., O\u2019Donnell R., Servedio R.A. (2004). J. Compu. Syst. Sci. 69, 421\u2013434","journal-title":"J. Compu. Syst. Sci."},{"key":"61_CR20","unstructured":"J. K\u00f6bler and W. Lindner, Bull. EATCS 89 (2006)."},{"key":"61_CR21","doi-asserted-by":"crossref","unstructured":"Y. Mansour, Learning Boolean functions via the Fourier transform, in Theoretical Advances in Neural Computation and Learning (Kluwer Academic Publishers, 1994, pp. 391\u2013424).","DOI":"10.1007\/978-1-4615-2696-4_11"},{"key":"61_CR22","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"Kushilevitz E., Mansour Y. (1993). SIAM J. Comput. 22, 1331\u20131348","journal-title":"SIAM J. Comput."},{"key":"61_CR23","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich O., Goldwasser S., Ron D. (1998). J. ACM 45, 653\u2013750","journal-title":"J. ACM"},{"key":"61_CR24","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld R., Sudan M. (1996). SIAM J. Comp. 25, 252\u2013271","journal-title":"SIAM J. Comp."},{"key":"61_CR25","doi-asserted-by":"crossref","unstructured":"Kahn J., Kalai G., and Linial N., in Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pp. 68\u201380 (1988).","DOI":"10.1109\/SFCS.1988.21923"},{"key":"61_CR26","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein E., Vazirani U. (1997). SIAM J. Comp 26, 1411\u20131473","journal-title":"SIAM J. Comp"},{"key":"61_CR27","unstructured":"R. O\u2019Donnell and R. A. Servedio, J. Comp System Sci, to appear. Available at http:\/\/www.cs.columbia.edu\/\u223crocco\/papers\/ccc03.htm .. Preliminary version appeared in Eighteenth Annual IEEE Conference on Computational Complexity, pp. 3\u201312 (2003)."},{"key":"61_CR28","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. Bshouty","year":"1996","unstructured":"Bshouty N., Cleve R., Gavald\u00e0 R., Kannan S., and Tamon C. (1996). J. Comp. Syst. Sci. 52, 421\u2013433","journal-title":"J. Comp. Syst. Sci."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-007-0061-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-007-0061-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-007-0061-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T21:01:09Z","timestamp":1737406869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-007-0061-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,2]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,10,10]]}},"alternative-id":["61"],"URL":"https:\/\/doi.org\/10.1007\/s11128-007-0061-6","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,2]]}}}