{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,3]],"date-time":"2023-09-03T09:11:47Z","timestamp":1693732307314},"reference-count":27,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2018,9,19]],"date-time":"2018-09-19T00:00:00Z","timestamp":1537315200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"publisher","award":["JP17H04676"],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2019,8]]},"abstract":"Abstract<\/jats:title>We characterize the set of properties of Boolean\u2010valued functions on a finite domain that are testable with a constant number of samples (x,f<\/jats:italic>(x<\/jats:italic>)) with x<\/jats:italic> drawn uniformly at random from . Specifically, we show that a property is testable with a constant number of samples if and only if it is (essentially) a k<\/jats:italic>\u2010part symmetric property for some constant k<\/jats:italic>, where a property is k<\/jats:italic>\u2010part symmetric if there is a partition of such that whether satisfies the property is determined solely by the densities of f<\/jats:italic> on . We use this characterization to show that symmetric properties are essentially the only graph properties and affine\u2010invariant properties that are testable with a constant number of samples and that for every constant , monotonicity of functions on the d<\/jats:italic>\u2010dimensional hypergrid is testable with a constant number of samples.<\/jats:p>","DOI":"10.1002\/rsa.20807","type":"journal-article","created":{"date-parts":[[2018,9,19]],"date-time":"2018-09-19T10:39:24Z","timestamp":1537353564000},"page":"73-88","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A characterization of constant\u2010sample testable properties"],"prefix":"10.1002","volume":"55","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science University of Waterloo Waterloo Canada"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[{"name":"Principles of Informatics Research Division, National Institute of Informatics Tokyo Japan"}]}],"member":"311","published-online":{"date-parts":[[2018,9,19]]},"reference":[{"key":"e_1_2_6_2_1","doi-asserted-by":"publisher","DOI":"10.3934\/amc.2007.1.239"},{"key":"e_1_2_6_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/060667177"},{"key":"e_1_2_6_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000292"},{"key":"e_1_2_6_5_1","doi-asserted-by":"crossref","unstructured":"M.\u2010F.Balcan E.Blais A.Blum andL.Yang Active property testing Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2012 pp.21\u201330.","DOI":"10.1109\/FOCS.2012.64"},{"key":"e_1_2_6_6_1","unstructured":"P.Berman M.Murzabulatov andS.Raskhodnikova Constant\u2010time testing and learning of image properties 2015."},{"key":"e_1_2_6_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20507"},{"key":"e_1_2_6_8_1","doi-asserted-by":"crossref","unstructured":"A.BhattacharyyaandY.Yoshida An algebraic characterization of testable Boolean CSPs Proceedings of the 40th International Colloquium Conference on Automata Languages and Programming (ICALP) 2013 pp.123\u2013134.","DOI":"10.1007\/978-3-642-39206-1_11"},{"key":"e_1_2_6_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/140971877"},{"key":"e_1_2_6_10_1","doi-asserted-by":"crossref","unstructured":"X.Chen R.A.Servedio andL.\u2010Y.Tan New algorithms and lower bounds for monotonicity testing Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2014 286\u2013295.","DOI":"10.1109\/FOCS.2014.38"},{"key":"e_1_2_6_11_1","volume-title":"Elements of information theory","author":"Cover T. M.","year":"2012"},{"key":"e_1_2_6_12_1","doi-asserted-by":"crossref","unstructured":"E.Fischer Y.Goldhirsh andO.Lachish Partial tests universal tests and decomposability Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS) 2014 483\u2013500.","DOI":"10.1145\/2554797.2554841"},{"key":"e_1_2_6_13_1","doi-asserted-by":"crossref","unstructured":"E.Fischer O.Lachish andY.Vasudev Trading query complexity for sample\u2010based testing and multi\u2010testing scalability Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2015 pp.1163\u20131182.","DOI":"10.1109\/FOCS.2015.75"},{"key":"e_1_2_6_14_1","doi-asserted-by":"crossref","unstructured":"E.Fischer E.Lehman I.Newman S.Raskhodnikova R.Rubinfeld andA.Samorodnitsky Monotonicity testing over general poset domains Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC) 2002 pp.474\u2013483.","DOI":"10.1145\/509907.509977"},{"key":"e_1_2_6_15_1","unstructured":"A. M.FriezeandR.Kannan The regularity lemma and approximation schemes for dense problems Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 1996 pp.12\u201320."},{"key":"e_1_2_6_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16367-8"},{"key":"e_1_2_6_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"e_1_2_6_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_6_19_1","doi-asserted-by":"crossref","unstructured":"O.GoldreichandD.Ron On sample\u2010based testers Proceedings of the 6th Conference on Innovations in Theoretical Computer Science (ITCS) 2015 337\u2013345.","DOI":"10.1145\/2688073.2688080"},{"key":"e_1_2_6_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"e_1_2_6_21_1","doi-asserted-by":"crossref","unstructured":"T.KaufmanandM.Sudan Algebraic property testing: The role of invariance Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC) 2008 403\u2013412.","DOI":"10.1145\/1374376.1374434"},{"key":"e_1_2_6_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1656"},{"key":"e_1_2_6_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_6_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"e_1_2_6_25_1","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-642-16367-8_12","volume-title":"Invariance in property testing","author":"Sudan M.","year":"2010"},{"issue":"1","key":"e_1_2_6_26_1","article-title":"Szemer\u00e9di's regularity lemma revisited","volume":"1","author":"Tao T.","year":"2006","journal-title":"Contrib. Discrete Math."},{"key":"e_1_2_6_27_1","unstructured":"L.Trevisan Entropy and the weak regularity lemma 2006.https:\/\/lucatrevisan.wordpress.com\/2006\/09\/10\/entropy--the-weak-regularity-lemma\/."},{"key":"e_1_2_6_28_1","doi-asserted-by":"crossref","unstructured":"Y.Yoshida A characterization of locally testable affine\u2010invariant properties via decomposition theorems Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC) 2014 154\u2013163.","DOI":"10.1145\/2591796.2591802"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20807","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20807","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T16:31:36Z","timestamp":1693672296000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20807"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,19]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["10.1002\/rsa.20807"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20807","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,19]]},"assertion":[{"value":"2017-09-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}