{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:24:07Z","timestamp":1772083447203,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,14]],"date-time":"2017-12-14T00:00:00Z","timestamp":1513209600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1422975"],"award-info":[{"award-number":["CCF-1422975"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Pennsylvania State University Graduate Fellowship"},{"name":"Pennsylvania State University College of Engineering Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us to surpass the (worst-case) lower bounds, expressed in terms of the input size, for several problems. Our aim is to develop a similar level of understanding of the complexity of sublinear-time algorithms to the one that was enabled by research in parameterized complexity for classical algorithms.<\/jats:p>\n          <jats:p>\n            Specifically, we focus on testing properties of functions. By parameterizing the query complexity in terms of the size\n            <jats:italic>r<\/jats:italic>\n            of the image of the input function, we obtain testers for monotonicity and convexity of functions of the form\n            <jats:italic>f<\/jats:italic>\n            :[\n            <jats:italic>n<\/jats:italic>\n            ]\u2192 R with query complexity\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>r<\/jats:italic>\n            ), with no dependence on\n            <jats:italic>n<\/jats:italic>\n            . The result for monotonicity circumvents the \u03a9 (log\n            <jats:italic>n<\/jats:italic>\n            ) lower bound by Fischer (Inf. Comput. 2004) for this problem. We present several other parameterized testers, providing compelling evidence that expressing the query complexity of property testers in terms of the input size is not always the best choice.\n          <\/jats:p>","DOI":"10.1145\/3155296","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T13:39:24Z","timestamp":1513345164000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Parameterized Property Testing of Functions"],"prefix":"10.1145","volume":"9","author":[{"given":"Ramesh Krishnan S.","family":"Pallavoor","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA"}]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}]},{"given":"Nithin","family":"Varma","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}]}],"member":"320","published-online":{"date-parts":[[2017,12,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.06.001"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","author":"Baleshzar Roksana"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.10.001"},{"key":"e_1_2_1_4_1","unstructured":"Mihir Bellare and Phillip Rogaway. 2005. Lecture Notes on Modern Cryptography. (2005). https:\/\/cseweb.ucsd.edu\/mihir\/cse207\/w-birthday.pdf.  Mihir Bellare and Phillip Rogaway. 2005. Lecture Notes on Modern Cryptography. (2005). https:\/\/cseweb.ucsd.edu\/mihir\/cse207\/w-birthday.pdf."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a016"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897567"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938584"},{"key":"e_1_2_1_8_1","volume-title":"36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016","author":"Berman Piotr","year":"2016"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry (SoCG\u201916)","author":"Berman Piotr","year":"2016"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591887"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/110826655"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.38"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2765-1"},{"key":"e_1_2_1_15_1","volume-title":"Encyclopedia of Algorithms","author":"Chakrabarty Deeparnab"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3039241"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488661"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a017"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/13092770X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746570"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.38"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Chen Xi"},{"key":"e_1_2_1_23_1","unstructured":"Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2001. Introduction to Algorithms 2nd ed. MIT Press and McGraw-Hill Book Company.   Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2001. Introduction to Algorithms 2nd ed. MIT Press and McGraw-Hill Book Company."},{"key":"e_1_2_1_24_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","author":"Dixit Kashyap","year":"2016"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/646976.711560"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.75"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/100789646"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898355"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645804"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554843"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/110840741"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.13"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3148"},{"key":"e_1_2_1_40_1","volume-title":"Property Testing - Current Research and Surveys {outgrow of a workshop at the Institute for Computer Science (ITCS) at","author":"Newman Ilan","year":"2010"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3155296"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702414026"},{"key":"e_1_2_1_43_1","volume-title":"Encyclopedia of Algorithms","author":"Raskhodnikova Sofya"},{"key":"e_1_2_1_44_1","first-page":"1","article-title":"A note on adaptivity in testing properties of bounded degree graphs","volume":"13","author":"Raskhodnikova Sofya","year":"2006","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897641"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/151002526"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155296","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3155296","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3155296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:28Z","timestamp":1750213588000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,14]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3155296"],"URL":"https:\/\/doi.org\/10.1145\/3155296","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,14]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}