{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:52:14Z","timestamp":1744217534199},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T00:00:00Z","timestamp":1451865600000},"content-version":"unspecified","delay-in-days":3,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>Given a property of Boolean functions, what is the minimum number of queries required to determine with high probability if an input function satisfies this property or is \u2018far\u2019 from satisfying it? This is a fundamental question in property testing, where traditionally the testing algorithm is allowed to pick its queries among the entire set of inputs. Balcan, Blais, Blum and Yang have recently suggested restricting the tester to take its queries from a smaller random subset of polynomial size of the inputs. This model is called <jats:italic>active testing<\/jats:italic>, and in the extreme case when the size of the set we can query from is exactly the number of queries performed, it is known as <jats:italic>passive testing<\/jats:italic>.<\/jats:p><jats:p>We prove that passive or active testing of <jats:italic>k<\/jats:italic>-linear functions (that is, sums of <jats:italic>k<\/jats:italic> variables among <jats:italic>n<\/jats:italic> over <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548315000292_inline1\" \/><jats:tex-math>$\\mathbb{Z}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sub>2<\/jats:sub>) requires \u0398(<jats:italic>k<\/jats:italic> log <jats:italic>n<\/jats:italic>) queries, assuming <jats:italic>k<\/jats:italic> is not too large. This extends the case <jats:italic>k<\/jats:italic> = 1, (that is, dictator functions), analysed by Balcan, Blais, Blum and Yang.<\/jats:p><jats:p>We also consider other classes of functions including low-degree polynomials, juntas, and partially symmetric functions. Our methods combine algebraic, combinatorial, and probabilistic techniques, including the Talagrand concentration inequality and the Erd\u0151s\u2013Rado theorem on \u0394-systems.<\/jats:p>","DOI":"10.1017\/s0963548315000292","type":"journal-article","created":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T09:35:33Z","timestamp":1451900133000},"page":"1-20","source":"Crossref","is-referenced-by-count":4,"title":["On Active and Passive Testing"],"prefix":"10.1017","volume":"25","author":[{"given":"NOGA","family":"ALON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RANI","family":"HOD","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"AMIT","family":"WEINSTEIN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,1,4]]},"reference":[{"key":"S0963548315000292_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"S0963548315000292_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"S0963548315000292_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.28"},{"key":"S0963548315000292_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"S0963548315000292_ref22","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-2010-029"},{"key":"S0963548315000292_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548315000292_ref18","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"S0963548315000292_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"S0963548315000292_ref27","first-page":"1134","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"S0963548315000292_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.54"},{"key":"S0963548315000292_ref16","doi-asserted-by":"crossref","unstructured":"Cohn D. , Atlas L. and Ladner R. (1994) Improving generalization with active learning. In Proc. 15th International Conference on Machine Learning: ICML '94, pp. 201\u2013221.","DOI":"10.1007\/BF00993277"},{"key":"S0963548315000292_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_26"},{"key":"S0963548315000292_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"S0963548315000292_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"S0963548315000292_ref21","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1656"},{"key":"S0963548315000292_ref4","doi-asserted-by":"crossref","unstructured":"Balcan M.-F. , Blais E. , Blum A. and Yang L. (2012) Active property testing. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science: FOCS '12, pp. 21\u201330.","DOI":"10.1109\/FOCS.2012.64"},{"key":"S0963548315000292_ref5","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"S0963548315000292_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.32"},{"key":"S0963548315000292_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0020-6"},{"key":"S0963548315000292_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536437"},{"key":"S0963548315000292_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_37"},{"key":"S0963548315000292_ref12","first-page":"551","article-title":"Partially symmetric functions are efficiently isomor-phism-testable","volume":"44","author":"Blais","year":"2012","journal-title":"Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science: FOCS '12"},{"key":"S0963548315000292_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.023"},{"key":"S0963548315000292_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"S0963548315000292_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"S0963548315000292_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"S0963548315000292_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02699376"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548315000292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T23:38:55Z","timestamp":1555717135000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548315000292\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["S0963548315000292"],"URL":"https:\/\/doi.org\/10.1017\/s0963548315000292","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}