{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:19:06Z","timestamp":1781259546132,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540853626","type":"print"},{"value":"9783540853633","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_26","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"317-330","source":"Crossref","is-referenced-by-count":25,"title":["Improved Bounds for Testing Juntas"],"prefix":"10.1007","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"5","key":"26_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":"3","key":"26_CR2","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."},{"issue":"6","key":"26_CR3","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1137\/0115129","volume":"15","author":"A.J. Bernstein","year":"1967","unstructured":"Bernstein, A.J.: Maximally connected arrays on the n-cube. SIAM J. Appl. Math.\u00a015(6), 1485\u20131489 (1967)","journal-title":"SIAM J. Appl. Math."},{"key":"26_CR4","unstructured":"Blum, A.: Relevant examples and relevant features: thoughts from computational learning theory. In: AAAI Fall Symposium on \u2018Relevance\u2019 (1994)"},{"key":"26_CR5","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":"2","key":"26_CR6","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"},{"key":"26_CR7","unstructured":"Bollob\u00e1s, B.: Combinatorics, Cambridge (1986)"},{"issue":"6","key":"26_CR8","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":"26_CR9","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":"4","key":"26_CR10","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."},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Gonen, M., Ron, D.: On the benefits of adaptivity in property testing of dense graphs. In: Proc. 11th Workshop RANDOM, pp. 525\u2013539 (2007)","DOI":"10.1007\/978-3-540-74208-1_38"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Guijarro, D., Tarui, J., Tsukiji, T.: Finding relevant variables in PAC model with membership queries. In: Proc. 10th Conference on Algorithmic Learning Theory, pp. 313\u2013322 (1999)","DOI":"10.1007\/3-540-46769-6_26"},{"issue":"1","key":"26_CR13","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"L.H. Harper","year":"1964","unstructured":"Harper, L.H.: Optimal assignments of numbers to vertices. SIAM J. Appl. Math.\u00a012(1), 131\u2013135 (1964)","journal-title":"SIAM J. Appl. Math."},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0012-365X(76)90058-3","volume":"14","author":"S. Hart","year":"1976","unstructured":"Hart, S.: A note on the edges of the n-cube. Disc. Math.\u00a014, 157\u2013163 (1976)","journal-title":"Disc. Math."},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., Linial, N.: The influence of variables on boolean functions. In: Proc. 29th Sym. on Foundations of Computer Science, pp. 68\u201380 (1988)","DOI":"10.1109\/SFCS.1988.21923"},{"key":"26_CR16","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"},{"issue":"3","key":"26_CR17","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":"26_CR18","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."},{"issue":"2","key":"26_CR19","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput.\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Probabilistic computations: towards a unified measure of complexity. In: Proc. 18th Sym. on Foundations of Comput. Sci., pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:35:08Z","timestamp":1619523308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}