{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:54:56Z","timestamp":1725854096727},"publisher-location":"New York, NY","reference-count":21,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_709","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:32:23Z","timestamp":1553095943000},"page":"2222-2226","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Testing Juntas and Related Properties of Boolean Functions"],"prefix":"10.1007","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"418_CR20117","unstructured":"Alon N, Hod R, Weinstein A (2013) On active and passive testing. arXiv preprint arXiv:13077364"},{"key":"418_CR20118","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1109\/FOCS.2012.64","volume-title":"IEEE 53rd annual symposium on foundations of computer science (FOCS\u201912), New Brunswick","author":"MF Balcan","year":"2012","unstructured":"Balcan MF, Blais E, Blum A, Yang L (2012) Active property testing. In: IEEE 53rd annual symposium on foundations of computer science (FOCS\u201912), New Brunswick. IEEE, pp\u00a021\u201330"},{"issue":"3","key":"418_CR20119","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 (1998) Free bits, PCPs, and nonapproximability\u2014towards tight results. SIAM J Comput 27(3):804\u2013915","journal-title":"SIAM J Comput"},{"key":"418_CR20120","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-540-85363-3_26","volume-title":"Approximation, randomization and combinatorial optimization","author":"E Blais","year":"2008","unstructured":"Blais E (2008) Improved bounds for testing juntas. In: Goel A, Jansen K, Rolim JDP, Rubinfeld R (eds) Approximation, randomization and combinatorial optimization. Algorithms and techniques. Springer, Boston, pp\u00a0317\u2013330"},{"key":"418_CR20121","first-page":"151","volume-title":"Proceedings of the 2009 ACM international symposium on theory of computing (STOC\u201909)","author":"E Blais","year":"2009","unstructured":"Blais E (2009) Testing juntas nearly optimally. In: Proceedings of the 2009 ACM international symposium on theory of computing (STOC\u201909). ACM, New York, pp\u00a0151\u2013157"},{"key":"418_CR20122","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-642-16367-8_4","volume-title":"Property testing \u2013 current research and surveys","author":"E Blais","year":"2010","unstructured":"Blais E (2010) Testing juntas: a brief survey. In: Goldreich O (ed) Property testing \u2013 current research and surveys. Springer, Berlin\/Heidelberg, pp\u00a032\u201340"},{"issue":"2","key":"418_CR20123","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00037-012-0040-x","volume":"21","author":"E Blais","year":"2012","unstructured":"Blais E, Brody J, Matulef K (2012) Property testing lower bounds via communication complexity. Comput Complex 21(2):311\u2013358","journal-title":"Comput Complex"},{"key":"418_CR20124","doi-asserted-by":"crossref","unstructured":"Blais E, Weinstein A, Yoshida Y (2012) Partially symmetric functions are efficiently isomorphism-testable. In: IEEE 53rd annual symposium on foundations of computer science (FOCS\u201912), New Brunswick, pp\u00a0551\u2013560","DOI":"10.1109\/FOCS.2012.53"},{"key":"418_CR20125","unstructured":"Blum A (1994) Relevant examples and relevant features: thoughts from computational learning theory. In: AAAI fall symposium on \u2018Relevance\u2019, New Orleans"},{"issue":"2","key":"418_CR20126","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 (1997) Selection of relevant features and examples in machine learning. Artif Intell 97(2):245\u2013271","journal-title":"Artif Intell"},{"issue":"1","key":"418_CR20127","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 (1995) Learning in the presence of finitely or infinitely many irrelevant attributes. J Comput Syst Sci 50(1):32\u201340","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"418_CR20128","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02785861","volume":"131","author":"J Bourgain","year":"2002","unstructured":"Bourgain J (2002) On the distribution of the fourier spectrum of boolean functions. Isr J Math 131(1):269\u2013276","journal-title":"Isr J Math"},{"key":"418_CR20129","unstructured":"Buhrman H, Garc\u00eda-Soriano D, Matsliah A, de\u00a0Wolf R (2013) The non-adaptive query complexity of testing k-parities. Chic J Theor Comput Sci 2013: Article 6, 11"},{"key":"418_CR20130","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/978-3-642-22006-7_46","volume-title":"Automata, languages and programming","author":"S Chakraborty","year":"2011","unstructured":"Chakraborty S, Garc\u00eda-Soriano D, Matsliah A (2011) Efficient sample extractors for juntas with applications. In: Aceto L, Henzinger M, Sgall J (eds) Automata, languages and programming. Springer, Zurich, pp\u00a0545\u2013556"},{"key":"418_CR20131","doi-asserted-by":"crossref","unstructured":"Chakraborty S, Fischer E, Garc\u00eda-Soriano D, Matsliah A (2012) Junto-symmetric functions, hypergraph isomorphism, and crunching. In: 2012 IEEE 27th conference on computational complexity (CCC\u201912). IEEE Computer Society, Los Alamitos, pp\u00a0148\u2013158","DOI":"10.1109\/CCC.2012.28"},{"issue":"6","key":"418_CR20132","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 (2004) A lower bound for testing juntas. Inf Process Lett 90(6):301\u2013305","journal-title":"Inf Process Lett"},{"key":"418_CR20133","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1109\/FOCS.2007.32","volume-title":"48th annual IEEE symposium on foundations of computer science (FOCS\u201907), Providence","author":"I Diakonikolas","year":"2007","unstructured":"Diakonikolas I, Lee HK, Matulef K, Onak K, Rubinfeld R, Servedio RA, Wan A (2007) Testing for concise representations. In: 48th annual IEEE symposium on foundations of computer science (FOCS\u201907), Providence. IEEE, pp\u00a0549\u2013558"},{"issue":"4","key":"418_CR20134","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 (2004) Testing juntas. J Comput System Sci 68(4):753\u2013787","journal-title":"J Comput System Sci"},{"issue":"1","key":"418_CR20135","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/PL00009809","volume":"18","author":"E Friedgut","year":"1998","unstructured":"Friedgut E (1998) Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18(1):27\u201335","journal-title":"Combinatorica"},{"issue":"4","key":"418_CR20136","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 (1998) Property testing and its connection to learning and approximation. J ACM 45(4):653\u2013750","journal-title":"J ACM"},{"issue":"1","key":"418_CR20137","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M Parnas","year":"2002","unstructured":"Parnas M, Ron D, Samorodnitsky A (2002) Testing basic boolean formulae. SIAM J Discret Math 16(1):20\u201346","journal-title":"SIAM J Discret Math"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_709","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:18:12Z","timestamp":1553098692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_709"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_709","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}