{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:39Z","timestamp":1750220079184,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CAREER","award":["CCF-0845701"],"award-info":[{"award-number":["CCF-0845701"]}]},{"name":"NSF award","award":["CCF-1422975, CCF-1909612"],"award-info":[{"award-number":["CCF-1422975, CCF-1909612"]}]},{"name":"Boston University\u2019s Hariri Institute for Computing and Center for Reliable Information Systems and Cyber Security"},{"name":"Simons Investigator grant to Salil Vadhan"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>We initiate a systematic study of tolerant testers of image properties or, equivalently, algorithms that approximate the distance from a given image to the desired property. Image processing is a particularly compelling area of applications for sublinear-time algorithms and, specifically, property testing. However, for testing algorithms to reach their full potential in image processing, they have to be tolerant, which allows them to be resilient to noise.<\/jats:p>\n          <jats:p>\n            We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so it becomes a half-plane? A representation of a convex object? A representation of a connected object? More precisely, our algorithms approximate the distance to three basic properties (being a half-plane, convexity, and connectedness) within a small additive error \u03b5, after reading\n            <jats:italic>poly<\/jats:italic>\n            (1\/\u03b5) pixels, independent of the image size. We also design an efficient agnostic proper PAC learner of convex sets (continuous and discrete) in two dimensions under the uniform distribution.\n          <\/jats:p>\n          <jats:p>\n            Our algorithms require very simple access to the input: uniform random samples for the half-plane property and convexity, and samples from uniformly random blocks for connectedness. However, the analysis of the algorithms, especially for convexity, requires many geometric and combinatorial insights. For example, in the analysis of the algorithm for convexity, we define a set of reference polygons\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>\u03b5<\/jats:sub>\n            such that (1) every convex image has a nearby polygon in\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>\u03b5<\/jats:sub>\n            and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>\u03b5<\/jats:sub>\n            .\n          <\/jats:p>","DOI":"10.1145\/3531527","type":"journal-article","created":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T11:13:47Z","timestamp":1652181227000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Tolerant Testers of Image Properties"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2363-3535","authenticated-orcid":false,"given":"Piotr","family":"Berman","sequence":"first","affiliation":[{"name":"Pennsylvania State University, PA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8329-7481","authenticated-orcid":false,"given":"Meiram","family":"Murzabulatov","sequence":"additional","affiliation":[{"name":"Nazarbayev University, Nur-Sultan city, Kazakhstan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4902-050X","authenticated-orcid":false,"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[{"name":"Boston University, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.83"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08796"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"2030","DOI":"10.1137\/1.9781611975994.125","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Belovs Aleksandrs","year":"2020","unstructured":"Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi. 2020. Functions over finite domains. In ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2030\u20132045."},{"key":"e_1_3_2_5_2","unstructured":"Talya Eden Ludmila Glinskih and Sofya Raskhodnikova. 2020. The problem of computing the distance to a connected image is NP-hard. In Personal Communication ."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.18"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.9"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.9"},{"key":"e_1_3_2_9_2","first-page":"90:1\u201390:14","volume-title":"43rd International Colloquium on Automata, Languages, and Programming (LIPIcs)","author":"Berman Piotr","year":"2016","unstructured":"Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. 2016. Tolerant testers of image properties. In 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.), Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 90:1\u201390:14."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0467-9"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20797"},{"key":"e_1_3_2_12_2","first-page":"164","volume-title":"ACM Symposium on Theory of Computing","author":"Berman Piotr","year":"2014","unstructured":"Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. 2014. \\( L_p \\) -testing. In ACM Symposium on Theory of Computing. 164\u2013173."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.18"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.38"},{"key":"e_1_3_2_15_2","article-title":"Machine learning theory","author":"Blum Avrim","year":"2012","unstructured":"Avrim Blum. 2012. Machine learning theory. Lecture notes. Retrieved from www.cs.cmu.edu\/avrim\/ML12\/lect0201.pdf.","journal-title":"Lecture notes"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_29"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_22"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45253-2_15"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1075661"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90002-3"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a009"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_3_2_27_2","article-title":"Sequential experimentation: Theory and principles","author":"Kleinberg Robert","year":"2020","unstructured":"Robert Kleinberg. 2020. Sequential experimentation: Theory and principles. Lecture notes. Retrieved from https:\/\/www.cs.cornell.edu\/courses\/cs6781\/2020sp\/lectures\/15_sequential-notes.pdf.","journal-title":"Lecture notes"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.165"},{"key":"e_1_3_2_29_2","article-title":"Tight approximation of image matching","volume":"1111","author":"Korman Simon","year":"2011","unstructured":"Simon Korman, Daniel Reichman, and Gilad Tsur. 2011. Tight approximation of image matching. CoRR abs\/1111.1713.","journal-title":"CoRR"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.302"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702414026"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_31"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/070701649"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21031"},{"key":"e_1_3_2_36_2","first-page":"1356","volume-title":"Symposium on Discrete Algorithms","author":"Raskhodnikova Sofya","year":"2013","unstructured":"Sofya Raskhodnikova and Grigory Yaroslavtsev. 2013. Learning pseudo-Boolean \\( k \\) -DNF and submodular functions. In Symposium on Discrete Algorithms. 1356\u20131368."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2635806"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55488-2_28"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9719-2"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531527","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:22Z","timestamp":1750183762000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3531527"],"URL":"https:\/\/doi.org\/10.1145\/3531527","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"2020-09-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}