{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T04:42:56Z","timestamp":1778647376960,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642163661","type":"print"},{"value":"9783642163678","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_4","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T11:25:55Z","timestamp":1286450755000},"page":"32-40","source":"Crossref","is-referenced-by-count":7,"title":["Testing Juntas: A Brief Survey"],"prefix":"10.1007","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"4_CR1","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s11128-007-0061-6","volume":"6","author":"A. At\u0131c\u0131","year":"2007","unstructured":"At\u0131c\u0131, A., Servedio, R.A.: Quantum algorithms for learning and testing juntas. Quantum Information Processing\u00a06(5), 323\u2013348 (2007)","journal-title":"Quantum Information Processing"},{"issue":"4","key":"4_CR2","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R. Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. of the ACM\u00a048(4), 778\u2013797 (2001)","journal-title":"J. of the ACM"},{"issue":"6","key":"4_CR3","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1109\/18.556674","volume":"42","author":"M. Bellare","year":"1996","unstructured":"Bellare, M., Coppersmith, D., H\u00e5stad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. IEEE Transactions on Information Theory\u00a042(6), 1781\u20131795 (1996)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"4_CR4","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and non-approximability \u2013 towards tight results. SIAM J. Comput.\u00a027(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-540-85363-3_26","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Blais","year":"2008","unstructured":"Blais, E.: Improved bounds for testing juntas. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 317\u2013330. Springer, Heidelberg (2008)"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proc. 41st Symposium on Theory of Computing, pp. 151\u2013158 (2009)","DOI":"10.1145\/1536414.1536437"},{"key":"4_CR7","unstructured":"Blum, A.: Relevant examples and relevant features: thoughts from computational learning theory. In: AAAI Fall Symposium on \u2018Relevance\u2019 (1994)"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A.: Learning a function of r relevant variables. In: Proc. 16th Conference on Computational Learning Theory, pp. 731\u2013733 (2003)","DOI":"10.1007\/978-3-540-45167-9_54"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1006\/jcss.1995.1004","volume":"50","author":"A. Blum","year":"1995","unstructured":"Blum, A., Hellerstein, L., Littlestone, N.: Learning in the presence of finitely or infinitely many irrelevant attributes. J. Comp. Syst. Sci.\u00a050(1), 32\u201340 (1995)","journal-title":"J. Comp. Syst. Sci."},{"issue":"2","key":"4_CR10","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0004-3702(97)00063-5","volume":"97","author":"A. Blum","year":"1997","unstructured":"Blum, A., Langley, P.: Selection of relevant features and examples in machine learning. Artificial Intelligence\u00a097(2), 245\u2013271 (1997)","journal-title":"Artificial Intelligence"},{"issue":"3","key":"4_CR11","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. Comput. Syst. Sci.\u00a047(3), 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR12","unstructured":"Buhrman, H., Fortnow, L., Newman, I., R\u00f6hrig, H.: Quantum property testing. In: Proc. 14th Symp. on Discrete Algorithms, pp. 480\u2013488 (2003)"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-16367-8_20","volume-title":"Property Testing","author":"V. Chen","year":"2010","unstructured":"Chen, V.: Query-Efficient dictatorship testing with perfect completeness. In: Goldreich, O. (ed.) Property Testing. LNCS, vol.\u00a06390, pp. 276\u2013279. Springer, Heidelberg (2010)"},{"issue":"6","key":"4_CR14","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.ipl.2004.01.023","volume":"90","author":"H. Chockler","year":"2004","unstructured":"Chockler, H., Gutfreund, D.: A lower bound for testing juntas. Information Processing Letters\u00a090(6), 301\u2013305 (2004)","journal-title":"Information Processing Letters"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Lee, H.K., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R.A., Wan, A.: Testing for concise representations. In: Proc. 48th Symposium on Foundations of Computer Science, pp. 549\u2013558 (2007)","DOI":"10.1109\/FOCS.2007.32"},{"issue":"3","key":"4_CR16","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1214\/aos\/1176345462","volume":"9","author":"B. Efron","year":"1981","unstructured":"Efron, B., Stein, C.: The jackknife estimate of variance. Ann. of Stat.\u00a09(3), 586\u2013596 (1981)","journal-title":"Ann. of Stat."},{"issue":"4","key":"4_CR17","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1016\/j.jcss.2003.11.004","volume":"68","author":"E. Fischer","year":"2004","unstructured":"Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. J. Comput. Syst. Sci.\u00a068(4), 753\u2013787 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. of the ACM"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-642-03685-9_39","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"O. Goldreich","year":"2009","unstructured":"Goldreich, O., Ron, D.: Algorithmic aspects of property testing in the dense graphs model. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX\u2013RANDOM 2009. LNCS, vol.\u00a05687, pp. 520\u2013533. Springer, Heidelberg (2009)"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-16367-8_23","volume-title":"Property Testing","author":"O. Goldreich","year":"2010","unstructured":"Goldreich, O., Ron, D.: Algorithmic aspects of property testing in the dense graphs model. In: Goldreich, O. (ed.) Property Testing. LNCS, vol.\u00a06390, pp. 295\u2013305. Springer, Heidelberg (2010)"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/978-3-540-74208-1_38","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Gonen","year":"2007","unstructured":"Gonen, M., Ron, D.: On the benefits of adaptivity in property testing of dense graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 525\u2013539. Springer, Heidelberg (2007)"},{"key":"4_CR22","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/3-540-46769-6_26","volume-title":"Algorithmic Learning Theory","author":"D. Guijarro","year":"1999","unstructured":"Guijarro, D., Tarui, J., Tsukiji, T.: Finding relevant variables in PAC model with membership queries. In: Watanabe, O., Yokomori, T. (eds.) ALT 1999. LNCS (LNAI), vol.\u00a01720, pp. 313\u2013322. Springer, Heidelberg (1999)"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A., Vishnoi, N.K.: On the Fourier spectrum of symmetric boolean functions with applications to learning symmetric juntas. In: Proc. 20th Conference on Computational Complexity, pp. 112\u2013119 (2005)","DOI":"10.1109\/CCC.2005.19"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Matulef, K., O\u2019Donnell, R., Rubinfeld, R., Servedio, R.A.: Testing halfspaces. In: Proc. 19th Symp. on Discrete Algorithms, pp. 256\u2013264 (2009)","DOI":"10.1137\/1.9781611973068.29"},{"issue":"3","key":"4_CR25","doi-asserted-by":"publisher","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.: Learning functions of k relevant variables. J. Comput. Syst. Sci.\u00a069(3), 421\u2013434 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"4_CR26","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M. Parnas","year":"2003","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic boolean formulae. SIAM J. Discret. Math.\u00a016(1), 20\u201346 (2003)","journal-title":"SIAM J. Discret. Math."},{"key":"4_CR27","unstructured":"Rubinfeld, R., Sudan, M.: Self-testing polynomial functions efficiently and over rational domains. In: Proc. 3rd Symp. on Discrete Algorithms, pp. 23\u201332 (1992)"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-642-16367-8_11","volume-title":"Property Testing","author":"R. Servedio","year":"2010","unstructured":"Servedio, R.: Testing by implicit learning: a brief survey. In: Goldreich, O. (ed.) Property Testing. LNCS, vol.\u00a06390, pp. 197\u2013210. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T11:18:23Z","timestamp":1553167103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}