{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:53:00Z","timestamp":1744217580665,"version":"3.37.3"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422975"],"award-info":[{"award-number":["CCF-1422975"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s00453-018-0467-9","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T14:10:00Z","timestamp":1533046200000},"page":"1247-1266","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Power and Limitations of Uniform Samples in Testing Properties of Figures"],"prefix":"10.1007","volume":"81","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1720-6913","authenticated-orcid":false,"given":"Meiram","family":"Murzabulatov","sequence":"additional","affiliation":[]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,31]]},"reference":[{"issue":"1","key":"467_CR1","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/060667177","volume":"39","author":"N Alon","year":"2009","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: It\u2019s all about regularity. SIAM J. Comput. 39(1), 143\u2013167 (2009)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"467_CR2","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0020-0190(79)90072-3","volume":"9","author":"AM Andrew","year":"1979","unstructured":"Andrew, A.M.: Another efficient algorithm for convex hulls in two dimensions. Inf. Process. Lett. 9(5), 216\u2013219 (1979)","journal-title":"Inf. Process. Lett."},{"key":"467_CR3","unstructured":"Baleshzar, R., Chakrabarty, D., Pallavoor, R.K.S., Raskhodnikova, S., Seshadhri, C.: Optimal unateness testers for real-valued functions: adaptivity helps. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10\u201314, 2017, Warsaw, Poland, Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, LIPIcs, vol.\u00a080, pp 5:1\u20135:14 (2017)"},{"key":"467_CR4","doi-asserted-by":"crossref","unstructured":"Batu, T., Dasgupta, S., Kumar, R., Rubinfeld, R.: The complexity of approximating the entropy. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 678\u2013687 (2002)","DOI":"10.1145\/509907.510005"},{"key":"467_CR5","unstructured":"Batu, T., Erg\u00fcn, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., Sami, R.: A sublinear algorithm for weakly approximating edit distance. In: Larmore, L.L., Goemans, M.X. (eds) Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9\u201311, 2003, San Diego, CA, USA, ACM, pp. 316\u2013324 (2003)"},{"issue":"1","key":"467_CR6","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/2432622.2432626","volume":"60","author":"T Batu","year":"2013","unstructured":"Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing closeness of discrete distributions. J. ACM 60(1), 4 (2013)","journal-title":"J. ACM"},{"issue":"1","key":"467_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E Ben-Sasson","year":"2005","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. SIAM J. Comput. 35(1), 1\u201321 (2005)","journal-title":"SIAM J. Comput."},{"key":"467_CR8","unstructured":"Berman, P., Raskhodnikova, S., Yaroslavtsev, G.: $$L_p$$-testing. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03, 2014, pp. 164\u2013173 (2014)"},{"key":"467_CR9","unstructured":"Berman, P., Murzabulatov, M., Raskhodnikova, S.: Testing convexity of figures under the uniform distribution. In: 32nd International Symposium on Computational Geometry, SoCG 2016, June 14\u201318, 2016, Boston, MA, USA, pp. 17:1\u201317:15 (2016)"},{"key":"467_CR10","unstructured":"Berman, P., Murzabulatov, M., Raskhodnikova, S.: The power and limitations of uniform samples in testing properties of figures. In: Lal, A., Akshay, S., Saurabh, S., Sen, S. (eds.) 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a065, pp. 45:1\u201345:14 (2016)"},{"key":"467_CR11","unstructured":"Berman, P., Murzabulatov, M., Raskhodnikova, S.: Tolerant testers of image properties. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11\u201315, 2016, Rome, Italy, pp. 90:1\u201390:14 (2016)"},{"issue":"3","key":"467_CR12","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. 47(3), 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"467_CR13","first-page":"63","volume":"22","author":"C Canonne","year":"2015","unstructured":"Canonne, C.: A survey on distribution testing: Your data is big. But is it blue? Electron. Colloq. Comput. Complex. (ECCC) 22, 63 (2015)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"467_CR14","unstructured":"Czumaj, A., Sohler, C.: Property testing with geometric queries. In: Algorithms\u2014ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28\u201331, 2001, Proceedings, pp. 266\u2013277 (2001)"},{"key":"467_CR15","unstructured":"Czumaj, A., Sohler, C., Ziegler, M.: Property testing in computational geometry. In: Algorithms\u2014ESA 2000, 8th Annual European Symposium, Saarbr\u00fccken, Germany, September 5\u20138, 2000, Proceedings, pp. 155\u2013166 (2000)"},{"key":"467_CR16","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonicity. In: Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM\u201999, Berkeley, CA, USA, pp. 97\u2013108 (1999)","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"467_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, vol. 10. Springer, Berlin (1987)"},{"issue":"3","key":"467_CR18","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F Erg\u00fcn","year":"2000","unstructured":"Erg\u00fcn, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. J Comput. Syst. Sci. 60(3), 717\u2013751 (2000)","journal-title":"J Comput. Syst. Sci."},{"key":"467_CR19","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: Reif, J.H. (ed) Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19\u201321, 2002, Montr\u00e9al, Qu\u00e9bec, Canada, pp. 474\u2013483. ACM (2002)","DOI":"10.1145\/509907.509977"},{"key":"467_CR20","unstructured":"Fischer, E., Lachish, O., Vasudev, Y.: Trading query complexity for sample-based testing and multi-testing scalability. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 October, 2015, pp. 1163\u20131182. IEEE Computer Society (2015)"},{"key":"467_CR21","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1090\/dimacs\/043\/04","volume":"43","author":"O Goldreich","year":"1999","unstructured":"Goldreich, O.: Combinatorial property testing (a survey). Randomization Methods Algorithm Des. 43, 45\u201359 (1999)","journal-title":"Randomization Methods Algorithm Des."},{"key":"467_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16367-8","volume-title":"Property Testing: Current Research and Surveys","author":"O Goldreich","year":"2010","unstructured":"Goldreich, O.: Property Testing: Current Research and Surveys, vol. 6390. Springer, Berlin (2010)"},{"key":"467_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252","volume-title":"Introduction to Property Testing","author":"O Goldreich","year":"2017","unstructured":"Goldreich, O.: Introduction to Property Testing. Cambridge University Press, Cambridge (2017)"},{"issue":"2","key":"467_CR24","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"key":"467_CR25","unstructured":"Goldreich, O., Ron, D.: On sample-based testers. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11\u201313, 2015, pp. 337\u2013345 (2015)"},{"issue":"4","key":"467_CR26","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. ACM 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"467_CR27","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica 20(3), 301\u2013337 (2000)","journal-title":"Combinatorica"},{"issue":"2","key":"467_CR28","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1137\/110840741","volume":"42","author":"M Jha","year":"2013","unstructured":"Jha, M., Raskhodnikova, S.: Testing and reconstruction of lipschitz functions with applications to data privacy. SIAM J. Comput. 42(2), 700\u2013731 (2013)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"467_CR29","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1109\/TPAMI.2010.165","volume":"33","author":"I Kleiner","year":"2011","unstructured":"Kleiner, I., Keren, D., Newman, I., Ben-Zwi, O.: Applying property testing to an image partitioning problem. IEEE Trans. Pattern Anal. Mach. Intell. 33(2), 256\u2013265 (2011)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"467_CR30","unstructured":"Korman, S., Reichman, D., Tsur, G.: Tight approximation of image matching. CoRR (2011). arXiv:1111.1713"},{"key":"467_CR31","unstructured":"Korman, S., Reichman, D., Tsur, G., Avidan, S.: Fast-match: Fast affine template matching. In: 2013 IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, June 23\u201328, 2013, pp. 2331\u20132338 (2013)"},{"issue":"2","key":"467_CR32","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s00453-009-9351-y","volume":"60","author":"O Lachish","year":"2011","unstructured":"Lachish, O., Newman, I.: Testing periodicity. Algorithmica 60(2), 401\u2013420 (2011)","journal-title":"Algorithmica"},{"issue":"3","key":"467_CR33","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0196-6774(85)90011-2","volume":"6","author":"N Megiddo","year":"1985","unstructured":"Megiddo, N.: Partitioning with two lines in the plane. J. Algorithms 6(3), 430\u2013433 (1985)","journal-title":"J. Algorithms"},{"key":"467_CR34","doi-asserted-by":"crossref","unstructured":"Newman, I., Rabinovich, Y., Rajendraprasad, D., Sohler, C.: Testing for forbidden order patterns in an array. In: Klein, P.N. (ed) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319, pp. 1582\u20131597. SIAM (2017)","DOI":"10.1137\/1.9781611974782.104"},{"issue":"4","key":"467_CR35","first-page":"17:1","volume":"9","author":"RKS Pallavoor","year":"2018","unstructured":"Pallavoor, R.K.S., Raskhodnikova, S., Varma, N.M.: Parameterized property testing of functions. TOCT 9(4), 17:1\u201317:19 (2018)","journal-title":"TOCT"},{"key":"467_CR36","doi-asserted-by":"crossref","unstructured":"Rademacher, L., Vempala, S.: Testing geometric convexity. In: FSTTCS, pp. 469\u2013480 (2004)","DOI":"10.1007\/978-3-540-30538-5_39"},{"key":"467_CR37","doi-asserted-by":"crossref","unstructured":"Raskhodnikova, S.: Approximate testing of visual properties. In: RANDOM-APPROX, pp. 370\u2013381 (2003)","DOI":"10.1007\/978-3-540-45198-3_31"},{"key":"467_CR38","doi-asserted-by":"crossref","unstructured":"Raskhodnikova, S.: Testing if an array is sorted. In: Encyclopedia of Algorithms, pp. 2219\u20132222 (2016)","DOI":"10.1007\/978-1-4939-2864-4_700"},{"key":"467_CR39","doi-asserted-by":"crossref","unstructured":"Raskhodnikova, S., Rubinfeld, R.: Linearity testing\/testing hadamard codes. In: Encyclopedia of Algorithms, pp. 1107\u20131110 (2016)","DOI":"10.1007\/978-1-4939-2864-4_202"},{"key":"467_CR40","unstructured":"Raskhodnikova, S., Smith, A.D.: A note on adaptivity in testing properties of bounded degree graphs. In: Electronic Colloquium on Computational Complexity (ECCC) 13(089) (2006). http:\/\/eccc.hpi-web.de\/eccc-reports\/2006\/TR06-089\/index.html"},{"issue":"3","key":"467_CR41","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1137\/070701649","volume":"39","author":"S Raskhodnikova","year":"2009","unstructured":"Raskhodnikova, S., Ron, D., Shpilka, A., Smith, A.: Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM. J. Comput. 39(3), 813\u2013842 (2009)","journal-title":"SIAM. J. Comput."},{"issue":"2","key":"467_CR42","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D Ron","year":"2010","unstructured":"Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci. 5(2), 73\u2013205 (2010)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"4","key":"467_CR43","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/2635806","volume":"10","author":"D Ron","year":"2014","unstructured":"Ron, D., Tsur, G.: Testing properties of sparse images. ACM Trans. Algorithms 10(4), 17:1\u201317:52 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"467_CR44","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/2331042.2331052","volume":"19","author":"R Rubinfeld","year":"2012","unstructured":"Rubinfeld, R.: Taming big probability distributions. ACM Crossroads 19(1), 24\u201328 (2012)","journal-title":"ACM Crossroads"},{"issue":"2","key":"467_CR45","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. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"467_CR46","doi-asserted-by":"crossref","unstructured":"Schmeltz, B.: Learning convex sets under uniform distribution. In: Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, pp. 204\u2013213 (1992)","DOI":"10.1007\/3-540-55488-2_28"},{"key":"467_CR47","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032770","volume-title":"Average Case Analysis of Algorithms on Sequences","author":"W Szpankowski","year":"2001","unstructured":"Szpankowski, W.: Average Case Analysis of Algorithms on Sequences. Wiley, New York (2001)"},{"key":"467_CR48","unstructured":"Tukey, J.W.: Mathematics and the picturing of data. In: Proceedings of the international congress of mathematicians, vol. 2, pp. 523\u2013531 (1975)"},{"issue":"6","key":"467_CR49","doi-asserted-by":"publisher","first-page":"1927","DOI":"10.1137\/080734066","volume":"40","author":"P Valiant","year":"2011","unstructured":"Valiant, P.: Testing symmetric properties of distributions. SIAM J. Comput. 40(6), 1927\u20131968 (2011)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0467-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0467-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0467-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,28]],"date-time":"2022-08-28T14:18:39Z","timestamp":1661696319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0467-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,31]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["467"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0467-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,7,31]]},"assertion":[{"value":"17 May 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}