[1]   Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu: Estimating the distance to a monotone function. Random Struct. Algor., 31(3):371–383, 2007. [doi:10.1002/rsa.20167]

[2]   Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron: Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032–4039, 2005. [doi:10.1109/TIT.2005.856958]

[3]   Sanjeev Arora and Madhu Sudan: Improved low-degree testing and its applications. Combinatorica, 23(3):365–426, 2003. [doi:10.1007/s00493-003-0025-0]

[4]   Pranjal Awasthi, Madhav Jha, Marco Molinaro, and Sofya Raskhodnikova: Testing Lipschitz functions on hypergrid domains. Algorithmica, 74(3):1055–1081, 2016. [doi:10.1007/s00453-015-9984-y]

[5]   László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy: Checking computations in polylogarithmic time. In Proc. 23rd STOC, pp. 21–31. ACM Press, 1991. [doi:10.1145/103418.103428]

[6]   László Babai, Lance Fortnow, and Carsten Lund: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity, 1(1):3–40, 1991. [doi:10.1007/BF01200056]

[7]   Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer: Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In Proc. 54th STOC, pp. 1671–1684. ACM Press, 2022. [doi:10.1145/3519935.3520064]

[8]   Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, and Madhu Sudan: Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795, 1996. [doi:10.1109/18.556674]

[9]   Mihir Bellare, Oded Goldreich, and Madhu Sudan: Free bits, PCPs, and nonapproximability–towards tight results. SIAM J. Comput., 27(3):804–915, 1998. [doi:10.1137/S0097539796302531]

[10]   Mihir Bellare, Shafi Goldwasser, Carsten Lund, and Alexander Russell: Efficient probabilistically checkable proofs and applications to approximations. In Proc. 25th STOC, pp. 294–304. ACM Press, 1993. [doi:10.1145/167088.167174]

[11]   Mihir Bellare and Madhu Sudan: Improved non-approximability results. In Proc. 26th STOC, pp. 184–193. ACM Press, 1994. [doi:10.1145/195058.195129]

[12]   Aleksandrs Belovs: Adaptive lower bound for testing monotonicity on the line. In Proc. 22nd Internat. Conf. on Randomization and Computation (RANDOM’18), pp. 31:1–10. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.31]

[13]   Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum: Hard properties with (very) short PCPPs and their applications. In Proc. 11th Innovations in Theoret. Comp. Sci. Conf. (ITCS’20), pp. 9:1–27. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.9]

[14]   Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev: A framework for adversarially robust streaming algorithms. J. ACM, 69(2):17:1–33, 2022. [doi:10.1145/3498334]

[15]   Omri Ben-Eliezer and Eylon Yogev: The adversarial robustness of sampling. In Proc. 39th Symp. on Principles of Database Systems (PODS’20), pp. 49–62. ACM Press, 2020. [doi:10.1145/3375395.3387643]

[16]   Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, and Avi Wigderson: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proc. 35th STOC, pp. 612–621. ACM Press, 2003. [doi:10.1145/780542.780631]

[17]   Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev: L_p-testing. In Proc. 46th STOC, pp. 164–173. ACM Press, 2014. [doi:10.1145/2591796.2591887]

[18]   Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff: Transitive-closure spanners. SIAM J. Comput., 41(6):1380–1425, 2012. [doi:10.1137/110826655]

[19]   Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman: Optimal testing of Reed-Muller codes. In Proc. 51st FOCS, pp. 488–497. IEEE Comp. Soc., 2010. A version of this paper, by the same title and authors, appeared as a chapter in “Property Testing: Current Research and Surveys” (Oded Goldreich, ed.), 2010, pp. 269–275, Springer LNCS vol. 6390. [doi:10.1109/FOCS.2010.54]

[20]   Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev: Lower bounds for testing properties of functions over hypergrid domains. In Proc. 29th IEEE Conf. on Comput. Complexity (CCC’14), pp. 309–320. IEEE Comp. Soc., 2014. [doi:10.1109/CCC.2014.38]

[21]   Manuel Blum, Michael Luby, and Ronitt Rubinfeld: Self-testing/correcting with applications to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. [doi:10.1016/0022-0000(93)90044-W]

[22]   Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri: Property testing on product distributions: Optimal testers for bounded derivative properties. ACM Trans. Algorithms, 13(2):20:1–30, 2017. [doi:10.1145/3039241]

[23]   Deeparnab Chakrabarty and C. Seshadhri: Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proc. 45th STOC, pp. 419–428. ACM Press, 2013. [doi:10.1145/2488608.2488661]

[24]   Deeparnab Chakrabarty and C. Seshadhri: An optimal lower bound for monotonicity testing over hypergrids. Theory of Computing, 10(17):453–464, 2014. [doi:10.4086/toc.2014.v010a017]

[25]   Irit Dinur and Venkatesan Guruswami: PCPs via low-degree long code and hardness for constrained hypergraph coloring. In Proc. 54th FOCS, pp. 340–349. IEEE Comp. Soc., 2013. [doi:10.1109/FOCS.2013.44]

[26]   Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, and Abhradeep Thakurta: Testing the Lipschitz property over product distributions with applications to data privacy. In Proc. Theory of Cryptography Conf. (TCC’13), pp. 418–436. Springer, 2013. [doi:10.1007/978-3-642-36594-2_24]

[27]   Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma: Erasure-resilient property testing. SIAM J. Comput., 47(2):295–329, 2018. [doi:10.1137/16M1075661]

[28]   Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky: Improved testing algorithms for monotonicity. In Proc. 3rd Internat. Workshop on Randomization and Computation (RANDOM’99), pp. 97–108. Springer, 1999. [doi:10.1007/978-3-540-48413-4_10]

[29]   Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan: Spot-checkers. J. Comput. System Sci., 60(3):717–751, 2000. [doi:10.1006/jcss.1999.1692]

[30]   Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy: Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268–292, 1996. [doi:10.1145/226643.226652]

[31]   Eldar Fischer: On the strength of comparisons in property testing. Inform. Comput., 189(1):107–116, 2004. [doi:10.1016/j.ic.2003.09.003]

[32]   Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky: Monotonicity testing over general poset domains. In Proc. 34th STOC, pp. 474–483. ACM Press, 2002. [doi:10.1145/509907.509977]

[33]   Katalin Friedl and Madhu Sudan: Some improvements to total degree tests. In Proc. 3rd Isr. Symp. Theory Comp. Sys. (ISTCS’95), pp. 190–198. IEEE Comp. Soc., 1995. [doi:10.1109/ISTCS.1995.377032]

[34]   Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson: Self-testing/correcting for polynomials and for approximate functions. In Proc. 23rd STOC, pp. 33–42. ACM Press, 1991. [doi:10.1145/103418.103429]

[35]   Oded Goldreich: On multiple input problems in property testing. In Proc. 18th Internat. Workshop on Randomization and Computation (RANDOM’14), pp. 704–720. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014. [doi:10.4230/LIPIcs.APPROX-RANDOM.2014.704]

[36]   Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky: Testing monotonicity. Combinatorica, 20(3):301–337, 2000. [doi:10.1007/s004930070011]

[37]   Oded Goldreich, Shafi Goldwasser, and Dana Ron: Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. [doi:10.1145/285055.285060]

[38]   Venkatesan Guruswami and Atri Rudra: Tolerant locally testable codes. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), pp. 306–317. Springer, 2005. [doi:10.1007/11538462_26]

[39]   Elad Haramaty, Amir Shpilka, and Madhu Sudan: Optimal testing of multivariate polynomials over small prime fields. SIAM J. Comput., 42(2):536–562, 2013. [doi:10.1137/120879257]

[40]   Johan Håstad and Avi Wigderson: Simple analysis of graph tests for linearity and PCP. Random Struct. Algor., 22(2):139–160, 2003. [doi:10.1002/rsa.10068]

[41]   Madhav Jha and Sofya Raskhodnikova: Testing and reconstruction of Lipschitz functions with applications to data privacy. SIAM J. Comput., 42(2):700–731, 2013. [doi:10.1137/110840741]

[42]   Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman: Testing low-degree polynomials over prime fields. Random Struct. Algor., 35(2):163–193, 2009. [doi:10.1002/rsa.20262]

[43]   Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma: Sublinear-time computation in the presence of online erasures. In Proc. 13th Innovations in Theoret. Comp. Sci. Conf. (ITCS’22), volume 215, pp. 90:1–25. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2022. [doi:10.4230/LIPIcs.ITCS.2022.90]

[44]   Tali Kaufman, Simon Litsyn, and Ning Xie: Breaking the ϵ-soundness bound of the linearity test over GF(2). SIAM J. Comput., 39(5):1988–2003, 2010. [doi:10.1137/080715548]

[45]   Tali Kaufman and Dana Ron: Testing polynomials over general fields. SIAM J. Comput., 36(3):779–802, 2006. [doi:10.1137/S0097539704445615]

[46]   Swastik Kopparty and Shubhangi Saraf: Tolerant linearity testing and locally testable codes. In Proc. 13th Internat. Workshop on Randomization and Computation (RANDOM’09), pp. 601–614. Springer, 2009. [doi:10.1007/978-3-642-03685-9_45]

[47]   Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma: Erasure-resilient sublinear-time graph algorithms. ACM Trans. Comput. Theory, 14(1):1–22, 2021. Preliminary version in ITCS’21. [doi:10.1145/3488250]

[48]   Alessandro Mantelero: The EU proposal for a general data protection regulation and the roots of the ‘right to be forgotten’. Computer Law & Security Review, 29(3):229–235, 2013. [doi:10.1016/j.clsr.2013.03.010]

[49]   Dana Moshkovitz: Low-degree test with polynomially small error. Comput. Complexity, 26(3):531–582, 2017. [doi:10.1007/s00037-016-0149-4]

[50]   Dana Moshkovitz and Ran Raz: Sub-constant error low degree test of almost-linear size. SIAM J. Comput., 38(1):140–180, 2008. [doi:10.1137/060656838]

[51]   Ilan Newman and Nithin Varma: New sublinear algorithms and lower bounds for LIS estimation. In Proc. 48th Internat. Colloq. on Automata, Languages, and Programming (ICALP’21), pp. 100:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.ICALP.2021.100]

[52]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014. [doi:10.1017/CBO9781139814782, arXiv:2105.10386]

[53]   Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma: Parameterized property testing of functions. ACM Trans. Comput. Theory, 9(4):17:1–19, 2018. [doi:10.1145/3155296]

[54]   Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Erik Waingarten: Approximating the distance to monotonicity of boolean functions. Random Struct. Algor., 60(2):233–260, 2022. [doi:10.1002/rsa.21029]

[55]   Ramesh Krishnan Pallavoor Suresh: Improved Algorithms and New Models in Property Testing. Ph. D. thesis, Boston University, 2020. OpenBU.

[56]   Michal Parnas, Dana Ron, and Ronitt Rubinfeld: Tolerant property testing and distance approximation. J. Comput. System Sci., 72(6):1012–1042, 2006. [doi:10.1016/j.jcss.2006.03.002]

[57]   Sofya Raskhodnikova: Testing if an array is sorted. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pp. 2219–2222. Springer, 2016. [doi:10.1007/978-1-4939-2864-4_700]

[58]   Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma: Erasures versus errors in local decoding and property testing. Random Struct. Algor., 59(4):640–670, 2021. [doi:10.1002/rsa.21031]

[59]   Sofya Raskhodnikova and Ronitt Rubinfeld: Linearity testing/Testing Hadamard codes. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pp. 1107–1110. Springer, 2016. [doi:10.1007/978-1-4939-2864-4_202]

[60]   Sofya Raskhodnikova and Adam D. Smith: A note on adaptivity in testing properties of bounded degree graphs. Electron. Colloq. Comput. Complexity, TR06-089, 2006. [ECCC]

[61]   Sofya Raskhodnikova and Nithin Varma: Brief announcement: Erasure-resilience versus tolerance to errors. In Proc. 45th Internat. Colloq. on Automata, Languages, and Programming (ICALP’18), pp. 111:1–3. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ICALP.2018.111]

[62]   Ran Raz and Shmuel Safra: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475–484. ACM Press, 1997. [doi:10.1145/258533.258641]

[63]   Noga Ron-Zewi and Madhu Sudan: A new upper bound on the query complexity of testing generalized Reed-Muller codes. Theory of Computing, 9(25):783–807, 2013. [doi:10.4086/toc.2013.v009a025]

[64]   Ronitt Rubinfeld and Madhu Sudan: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996. [doi:10.1137/S0097539793255151]

[65]   Michael E. Saks and C. Seshadhri: Estimating the longest increasing sequence in polylogarithmic time. SIAM J. Comput., 46(2):774–823, 2017. [doi:10.1137/130942152]

[66]   Alex Samorodnitsky: Low-degree tests at large distances. In Proc. 39th STOC, pp. 506–515. ACM Press, 2007. [doi:10.1145/1250790.1250864]

[67]   Alex Samorodnitsky and Luca Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2000. [doi:10.1145/335305.335329]

[68]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. SIAM J. Comput., 39(1):323–360, 2009. [doi:10.1137/070681612]

[69]   Amir Shpilka and Avi Wigderson: Derandomizing homomorphism testing in general groups. SIAM J. Comput., 36(4):1215–1230, 2006. [doi:10.1137/S009753970444658X]

[70]   Madhu Sudan and Luca Trevisan: Probabilistically checkable proofs with low amortized query complexity. In Proc. 39th FOCS, pp. 18–27. IEEE Comp. Soc., 1998. [doi:10.1109/SFCS.1998.743425]

[71]   Luca Trevisan: Recycling queries in PCPs and in linearity tests (extended abstract). In Proc. 30th STOC, pp. 299–308. ACM Press, 1998. [doi:10.1145/276698.276769]

[72]   Andrew Chi-Chih Yao: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In Proc. 18th FOCS, pp. 222–227. IEEE Comp. Soc., 1977. [doi:10.1109/SFCS.1977.24]