{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T16:53:33Z","timestamp":1773420813962,"version":"3.50.1"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>\n                    The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova, and Varma (Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Our main contributions are as follows:\n                    <jats:list list-type=\"simple\">\n                      <jats:list-item>\n                        <jats:label>\u2014<\/jats:label>\n                        <jats:p>\n                          An extension of the model, introducing\n                          <jats:italic toggle=\"yes\">batch queries<\/jats:italic>\n                          where multiple queries are made and answered between each round of manipulation, and\n                          <jats:italic toggle=\"yes\">fractional manipulation rate<\/jats:italic>\n                          , where the adversary makes less than one manipulation per round.\n                        <\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:label>\u2014<\/jats:label>\n                        <jats:p>New optimal testers for linearity of Boolean functions in the original online and offline models.<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:label>\u2014<\/jats:label>\n                        <jats:p>A new lower bound in the original model for testing whether a Boolean function has low degree and an algorithm using batch queries that overcomes it.<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:label>\u2014<\/jats:label>\n                        <jats:p>Efficient testers for local properties of sequences when the manipulation rate is fractional. Specifically, for sortedness, we show a sharp transition from optimal query complexity to the impossibility of testability, depending on the manipulation rate.<\/jats:p>\n                      <\/jats:list-item>\n                    <\/jats:list>\n                  <\/jats:p>","DOI":"10.1145\/3778165","type":"journal-article","created":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T11:03:33Z","timestamp":1764673413000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Property Testing with Online Adversaries"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6366-5964","authenticated-orcid":false,"given":"Omri","family":"Ben-Eliezer","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology","place":["Cambridge, United States"]},{"name":"Technion\u2013Israel Institute of Technology","place":["Haifa, Israel"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4962-848X","authenticated-orcid":false,"given":"Esty","family":"Kelman","sequence":"additional","affiliation":[{"name":"CS and CDS, Boston University","place":["Boston, United States"]},{"name":"Massachusetts Institute of Technology","place":["Cambridge, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4274-346X","authenticated-orcid":false,"given":"Uri","family":"Meir","sequence":"additional","affiliation":[{"name":"Tel Aviv University","place":["Tel Aviv, Israel"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4902-050X","authenticated-orcid":false,"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[{"name":"Boston University","place":["Boston, United States"]}]}],"member":"320","published-online":{"date-parts":[[2026,2,25]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","unstructured":"Noga Alon Tali Kaufman Michael Krivelevich Simon Litsyn and Dana Ron. 2005. Testing Reed-Muller codes. IEEE Transactions on Information Theory 51 11 (2005) 4032\u20134039. DOI:10.1109\/TIT.2005.856958","DOI":"10.1109\/TIT.2005.856958"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Madhu Sudan. 2003. Improved low-degree testing and its applications. Combinatorica 23 3 (2003) 365\u2013426. DOI:10.1007\/s00493-003-0025-0","DOI":"10.1007\/s00493-003-0025-0"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978315.5"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","unstructured":"Pranjal Awasthi Madhav Jha Marco Molinaro and Sofya Raskhodnikova. 2016. Testing Lipschitz functions on hypergrid domains. Algorithmica 74 3 (2016) 1055\u20131081. DOI:10.1007\/s00453-015-9984-y","DOI":"10.1007\/s00453-015-9984-y"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Babai Lance Fortnow and Carsten Lund. 1991. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1 (1991) 3\u201340. DOI:10.1007\/BF01200056","DOI":"10.1007\/BF01200056"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511735202"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","unstructured":"Mihir Bellare Don Coppersmith Johan H\u00e5stad Marcos A. Kiwi and Madhu Sudan. 1996. Linearity testing in characteristic two. IEEE Transactions on Information Theory 42 6 (1996) 1781\u20131795. DOI:10.1109\/18.556674","DOI":"10.1109\/18.556674"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","unstructured":"Mihir Bellare Oded Goldreich and Madhu Sudan. 1998. Free bits PCPs and non-approximability - towards tight results. SIAM Journal on Computing 27 3 (1998) 804\u2013915. DOI:10.1137\/S0097539796302531","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195129"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.31"},{"key":"e_1_3_4_14_2","doi-asserted-by":"crossref","unstructured":"Ido Ben-Eliezer Rani Hod and Shachar Lovett. 2012. Random low-degree polynomials are hard to approximate. Computational Complexity 21 1 (2012) 63\u201381.","DOI":"10.1007\/s00037-011-0020-6"},{"key":"e_1_3_4_15_2","first-page":"11:1\u201311:20","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS)","author":"Ben-Eliezer Omri","year":"2019","unstructured":"Omri Ben-Eliezer. 2019. Testing local properties of arrays. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS). 11:1\u201311:20."},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.9"},{"key":"e_1_3_4_17_2","first-page":"11:1\u201311:25","volume-title":"Proceedings of the 15th Innovations in Theoretical Computer Science Conference (ITCS)","author":"Ben-Eliezer Omri","year":"2024","unstructured":"Omri Ben-Eliezer, Esty Kelman, Uri Meir, and Sofya Raskhodnikova. 2024. Property testing with online adversaries. In Proceedings of the 15th Innovations in Theoretical Computer Science Conference (ITCS). 11:1\u201311:25."},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591887"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","unstructured":"Arnab Bhattacharyya Elena Grigorescu Kyomin Jung Sofya Raskhodnikova and David P. Woodruff. 2012. Transitive-closure spanners. SIAM Journal on Computing 41 6 (2012) 1380\u20131425. DOI:10.1137\/110826655","DOI":"10.1137\/110826655"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.54"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","unstructured":"Manuel Blum Michael Luby and Ronitt Rubinfeld. 1993. Self-testing\/correcting with applications to numerical problems. Journal of Computer and System Sciences 47 3 (1993) 549\u2013595. DOI:10.1016\/0022-0000(93)90044-W","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","unstructured":"Deeparnab Chakrabarty Kashyap Dixit Madhav Jha and C. Seshadhri. 2017. Property testing on product distributions: Optimal testers for bounded derivative properties. ACM Transactions on Algorithms 13 2 (2017) 20:1\u201320:30. DOI:10.1145\/3039241","DOI":"10.1145\/3039241"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488661"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","unstructured":"Deeparnab Chakrabarty and C. Seshadhri. 2014. An optimal lower bound for monotonicity testing over hypergrids. Theory of Computing 10 (2014) 453\u2013464. DOI:10.4086\/toc.2014.v010a017","DOI":"10.4086\/toc.2014.v010a017"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.44"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_24"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","unstructured":"Kashyap Dixit Sofya Raskhodnikova Abhradeep Thakurta and Nithin Varma. 2018. Erasure-resilient property testing. SIAM Journal on Computing 47 2 (2018) 295\u2013329. DOI:10.1137\/16M1075661","DOI":"10.1137\/16M1075661"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","unstructured":"Funda Erg\u00fcn Sampath Kannan Ravi Kumar Ronitt Rubinfeld and Mahesh Viswanathan. 2000. Spot-checkers. Journal of Computer and System Sciences 60 3 (2000) 717\u2013751. DOI:10.1006\/jcss.1999.1692","DOI":"10.1006\/jcss.1999.1692"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","unstructured":"Uriel Feige Shafi Goldwasser L\u00e1szl\u00f3 Lov\u00e1sz Shmuel Safra and Mario Szegedy. 1996. Interactive proofs and the hardness of approximating cliques. Journal of the ACM 43 2 (1996) 268\u2013292. DOI:10.1145\/226643.226652","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","unstructured":"Eldar Fischer. 2004. On the strength of comparisons in property testing. Information and Computation 189 1 (2004) 107\u2013116. DOI:10.1016\/j.ic.2003.09.003","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1995.377032"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103429"},{"key":"e_1_3_4_35_2","doi-asserted-by":"crossref","unstructured":"Oded Goldreich and Dana Ron. 2017. On learning and testing dynamic environments. Journal of the ACM 64 3 (2017) 1\u201390.","DOI":"10.1145\/3088509"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","unstructured":"Elad Haramaty Amir Shpilka and Madhu Sudan. 2013. Optimal testing of multivariate polynomials over small prime fields. SIAM Journal on Computing 42 2 (2013) 536\u2013562. DOI:10.1137\/120879257","DOI":"10.1137\/120879257"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","unstructured":"Johan H\u00e5stad and Avi Wigderson. 2003. Simple analysis of graph tests for linearity and PCP. Random Structures and Algorithms 22 2 (2003) 139\u2013160. DOI:10.1002\/rsa.10068","DOI":"10.1002\/rsa.10068"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0825-5"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","unstructured":"Madhav Jha and Sofya Raskhodnikova. 2013. Testing and reconstruction of Lipschitz functions with applications to data privacy. SIAM Journal on Computing 42 2 (2013) 700\u2013731. DOI:10.1137\/110840741","DOI":"10.1137\/110840741"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","unstructured":"Charanjit S. Jutla Anindya C. Patthak Atri Rudra and David Zuckerman. 2009. Testing low-degree polynomials over prime fields. Random Structures and Algorithms 35 2 (2009) 163\u2013193. DOI:10.1002\/rsa.20262","DOI":"10.1002\/rsa.20262"},{"key":"#cr-split#-e_1_3_4_41_2.1","doi-asserted-by":"crossref","unstructured":"Iden Kalemaj Sofya Raskhodnikova and Nithin Varma. 2023. Sublinear-time computation in the presence of online erasures. Theory of Computing 19","DOI":"10.4086\/toc.2023.v019a001"},{"key":"#cr-split#-e_1_3_4_41_2.2","unstructured":"(1) (2023) 1-48. Retrieved from http:\/\/theoryofcomputing.org\/articles\/v019a001\/"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","unstructured":"Tali Kaufman Simon Litsyn and Ning Xie. 2010. Breaking the epsilon-soundness bound of the linearity test over gf(2). SIAM Journal on Computing 39 5 (2010) 1988\u20132003. DOI:10.1137\/080715548","DOI":"10.1137\/080715548"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00017"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","unstructured":"Tali Kaufman and Dana Ron. 2006. Testing polynomials over general fields. SIAM Journal on Computing 36 3 (2006) 779\u2013802. DOI:10.1137\/S0097539704445615","DOI":"10.1137\/S0097539704445615"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374434"},{"key":"e_1_3_4_46_2","doi-asserted-by":"crossref","unstructured":"Peter Keevash and Benny Sudakov. 2005. Set systems with restricted cross-intersections and the minimum rank ofinclusion matrices. SIAM Journal on Discrete Mathematics 18 4 (2005) 713\u2013727.","DOI":"10.1137\/S0895480103434634"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.80"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.154"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","unstructured":"Dana Moshkovitz. 2017. Low-degree test with polynomially small error. Computational Complexity 26 3 (2017) 531\u2013582. DOI:10.1007\/s00037-016-0149-4","DOI":"10.1007\/s00037-016-0149-4"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","unstructured":"Dana Moshkovitz and Ran Raz. 2008. Sub-constant error low degree test of almost-linear size. SIAM Journal on Computing 38 1 (2008) 140\u2013180. DOI:10.1137\/060656838","DOI":"10.1137\/060656838"},{"key":"e_1_3_4_51_2","first-page":"98:1\u201398:20","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Nakar Yonatan","year":"2021","unstructured":"Yonatan Nakar and Dana Ron. 2021. Testing dynamic environments: Back to basics. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP). 98:1\u201398:20."},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.100"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","unstructured":"Ramesh Krishnan S. Pallavoor Sofya Raskhodnikova and Nithin Varma. 2018. Parameterized property testing of functions. ACM Transactions on Computation Theory 9 4 (2018) 17:1\u201317:19. DOI:10.1145\/3155296","DOI":"10.1145\/3155296"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","unstructured":"Ramesh Krishnan S. Pallavoor Sofya Raskhodnikova and Erik Waingarten. 2022. Approximating the distance to monotonicity of Boolean functions. Random Structures and Algorithms 60 2 (2022) 233\u2013260. DOI:10.1002\/rsa.21029","DOI":"10.1002\/rsa.21029"},{"key":"e_1_3_4_56_2","unstructured":"Sofya Raskhodnikova. 1999. Monotonicity testing. Masters Thesis MIT (1999) 42."},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","unstructured":"Sofya Raskhodnikova. 2016. Testing if an array is sorted. Encyclopedia of Algorithms (2016) 2219\u20132222. DOI:10.1007\/978-1-4939-2864-4_700","DOI":"10.1007\/978-1-4939-2864-4_700"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","unstructured":"Sofya Raskhodnikova Noga Ron-Zewi and Nithin Varma. 2021. Erasures versus errors in local decoding and property testing. Random Structures and Algorithms 59 4 (2021) 640\u2013670. DOI:10.1002\/rsa.21031","DOI":"10.1002\/rsa.21031"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_202"},{"key":"e_1_3_4_60_2","first-page":"111:1\u2013111:3","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Raskhodnikova Sofya","year":"2018","unstructured":"Sofya Raskhodnikova and Nithin Varma. 2018. Brief announcement: Erasure-resilience versus tolerance to errors. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP). 111:1\u2013111:3."},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","unstructured":"Noga Ron-Zewi and Madhu Sudan. 2013. A new upper bound on the query complexity of testing generalized Reed-Muller codes. Theory of Computing 9 (2013) 783\u2013807. DOI:10.4086\/toc.2013.v009a025","DOI":"10.4086\/toc.2013.v009a025"},{"key":"e_1_3_4_63_2","doi-asserted-by":"publisher","unstructured":"Ronitt Rubinfeld and Madhu Sudan. 1996. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing 25 2 (1996) 252\u2013271. DOI:10.1137\/S0097539793255151","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_4_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250864"},{"key":"e_1_3_4_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_3_4_66_2","doi-asserted-by":"publisher","unstructured":"Alex Samorodnitsky and Luca Trevisan. 2009. Gowers uniformity influence of variables and PCPs. SIAM Journal on Computing 39 1 (2009) 323\u2013360. DOI:10.1137\/070681612","DOI":"10.1137\/070681612"},{"key":"e_1_3_4_67_2","doi-asserted-by":"publisher","unstructured":"Amir Shpilka and Avi Wigderson. 2006. Derandomizing homomorphism testing in general groups. SIAM Journal on Computing 36 4 (2006) 1215\u20131230. DOI:10.1137\/S009753970444658X","DOI":"10.1137\/S009753970444658X"},{"key":"e_1_3_4_68_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743425"},{"key":"e_1_3_4_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276769"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3778165","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T15:02:01Z","timestamp":1773414121000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3778165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,25]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3778165"],"URL":"https:\/\/doi.org\/10.1145\/3778165","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,25]]},"assertion":[{"value":"2024-04-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}