[1]   Nir Ailon and Bernard Chazelle: Information theory in property testing and monotonicity testing in higher dimension. Inform. and Comput., 204(11):1704–1717, 2006. Preliminary version in STACS’05. [doi:10.1016/j.ic.2006.06.001]

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

[3]   Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri: A lower bound for nonadaptive, one-sided error testing of unateness of Boolean functions over the hypercube. Electron. Colloq. on Comput. Complexity (ECCC), 2017. [ECCC:TR17-111, arXiv:1706.00053]

[4]   Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri: Optimal unateness testers for real-valued functions: Adaptivity helps. In Proc. 44th Internat. Colloq. on Automata, Languages and Programming (ICALP’17), pp. 5:1–5:14. Springer, 2017. [doi:10.4230/LIPIcs.ICALP.2017.5, arXiv:1703.05199]

[5]   Tuğkan Batu, Ronitt Rubinfeld, and Patrick White: Fast approximate PCPs for multidimensional bin-packing problems. Inform. and Comput., 196(1):42–56, 2005. Preliminary version in RANDOM’99. [doi:10.1016/j.ic.2004.10.001]

[6]   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. Preliminary version in FOCS’95. [doi:10.1109/18.556674]

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

[8]   Aleksandrs Belovs and Eric Blais: Quantum algorithm for monotonicity testing on the hypercube. Theory of Computing, 11(16):403–412, 2015. [doi:10.4086/toc.2015.v011a016, arXiv:1503.02868]

[9]   Aleksandrs Belovs and Eric Blais: A polynomial lower bound for testing monotonicity. In Proc. 48th STOC, pp. 1021–1032. ACM Press, 2016. [doi:10.1145/2897518.2897567, arXiv:1511.05053]

[10]   Michael Ben-Or, Don Coppersmith, Michael Luby, and Ronitt Rubinfeld: Non-abelian homomorphism testing, and distributions close to their self-convolutions. Random Structures Algorithms, 32(1):49–70, 2008. Preliminary version in RANDOM’04. [doi:10.1002/rsa.20182]

[11]   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]

[12]   Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff: Transitive-closure spanners. SIAM J. Comput., 41(6):1380–1425, 2012. Preliminary version in SODA’09. [doi:10.1137/110826655, arXiv:0808.1787]

[13]   Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri: A o(d)⋅ polylog(n) monotonicity tester for Boolean functions over the hypergrid [n]^d. In Proc. 29th ACM-SIAM Symp. on Discrete Algorithms (SODA’18), pp. 2133–2151. ACM Press, 2018. [doi:10.1137/1.9781611975031.139, arXiv:1710.10545]

[14]   Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri: Domain reduction for monotonicity testing: A o(d) tester for Boolean functions in d-dimensions. In Proc. 31st ACM-SIAM Symp. on Discrete Algorithms (SODA’20), pp. 1975–1994. ACM Press, 2020. [doi:10.1137/1.9781611975994.122, arXiv:1811.01427]

[15]   Eric Blais and Abhinav Bommireddi: Testing submodularity and other properties of valuation functions. In Proc. 8th Innovations in Theoret. Computer Science (ITCS’17), pp. 33:1–33:17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.33, arXiv:1611.07879]

[16]   Eric Blais, Joshua Brody, and Kevin Matulef: Property testing lower bounds via communication complexity. Comput. Complexity, 21(2):311–358, 2012. Preliminary version in CCC’11. [doi:10.1007/s00037-012-0040-x]

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

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

[19]   Jop Briët, Sourav Chakraborty, David García-Soriano, and Arie Matsliah: Monotonicity testing and shortest-path routing on the cube. Combinatorica, 32(1):35–53, 2012. Preliminary version in RANDOM’10. [doi:10.1007/s00493-012-2765-1]

[20]   Deeparnab Chakrabarty: Monotonicity testing. In Encyclopedia of Algorithms, pp. 1352–1356. Springer, 2016. [doi:10.1007/978-1-4939-2864-4_699]

[21]   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–20:30, 2017. Preliminary version in SODA’15. [doi:10.1145/3039241, arXiv:1404.0718]

[22]   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, arXiv:1204.0849]

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

[24]   Deeparnab Chakrabarty and C. Seshadhri: An o(n) monotonicity tester for Boolean functions over the hypercube. SIAM J. Comput., 45(2):461–472, 2016. Preliminary version in STOC’13. [doi:10.1137/13092770X, arXiv:1302.4536]

[25]   Deeparnab Chakrabarty and C. Seshadhri: Adaptive Boolean monotonicity testing in total influence time. In Proc. 10th Innovations in Theoret. Computer Science (ITCS’19), pp. 20:1–20:7. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.20, arXiv:1801.02816]

[26]   Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan: Boolean function monotonicity testing requires (almost) n^1∕2 non-adaptive queries. In Proc. 47th STOC, pp. 519–528. ACM Press, 2015. [doi:10.1145/2746539.2746570, arXiv:1412.5657]

[27]   Xi Chen, Rocco A. Servedio, and Li-Yang Tan: New algorithms and lower bounds for monotonicity testing. In Proc. 55th FOCS, pp. 286–295. IEEE Comp. Soc. Press, 2014. [doi:10.1109/FOCS.2014.38, arXiv:1412.5655]

[28]   Xi Chen and Erik Waingarten: Testing unateness nearly optimally. In Proc. 51st STOC, pp. 547–558. ACM Press, 2019. [doi:10.1145/3313276.3316351, arXiv:1904.05309]

[29]   Xi Chen, Erik Waingarten, and Jinyu Xie: Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. In Proc. 49th STOC, pp. 523–536. ACM Press, 2017. [doi:10.1145/3055399.3055461, arXiv:1702.06997]

[30]   Xi Chen, Erik Waingarten, and Jinyu Xie: Boolean unateness testing with (n^3∕4) adaptive queries. In Proc. 58th FOCS, pp. 868–879. IEEE Comp. Soc. Press, 2017. [doi:10.1109/FOCS.2017.85, arXiv:1708.05786]

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

[32]   Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin M. Varma: Erasure-resilient property testing. SIAM J. Comput., 47(2):295–329, 2018. Preliminary version in ICALP’16. [doi:10.1137/16M1075661, arXiv:1607.05786]

[33]   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]

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

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

[36]   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]

[37]   Oded Goldreich: Introduction to Property Testing. Cambridge Univ. Press, 2017. [doi:10.1017/9781108135252]

[38]   Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky: Testing monotonicity. Combinatorica, 20(3):301–337, 2000. Preliminary version in FOCS’98. [doi:10.1007/s004930070011]

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

[40]   Oded Goldreich and Dana Ron: On proximity-oblivious testing. SIAM J. Comput., 40(2):534–566, 2011. Preliminary version in STOC’09. [doi:10.1137/100789646]

[41]   Shirley Halevy and Eyal Kushilevitz: Distribution-free property-testing. SIAM J. Comput., 37(4):1107–1138, 2007. Preliminary version in RANDOM’03. [doi:10.1137/050645804]

[42]   Shirley Halevy and Eyal Kushilevitz: Testing monotonicity over graph products. Random Structures Algorithms, 33(1):44–67, 2008. Preliminary version in ICALP’04. [doi:10.1002/rsa.20211]

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

[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. Preliminary version in RANDOM’08. [doi:10.1137/080715548]

[45]   Subhash Khot, Dor Minzer, and Muli Safra: On monotonicity testing and Boolean isoperimetric-type theorems. SIAM J. Comput., 47(6):2238–2276, 2018. Preliminary version in FOCS’15. [doi:10.1137/16M1065872]

[46]   Subhash Khot and Igor Shinkar: An (n) queries adaptive tester for unateness. In Proc. 20th Internat. Workshop on Randomization and Computation (RANDOM’16), pp. 37:1–37:7. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.APPROX-RANDOM.2016.37, arXiv:1608.02451]

[47]   Eric Lehman and Dana Ron: On disjoint chains of subsets. J. Combin. Theory Ser. A, 94(2):399–404, 2001. [doi:10.1006/jcta.2000.3148]

[48]   Amit Levi and Erik Waingarten: Lower bounds for tolerant junta and unateness testing via rejection sampling of graphs. In Proc. 10th Innovations in Theoret. Computer Science (ITCS’19), pp. 52:1–52:20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.52, arXiv:1805.01074]

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

[50]   Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Erik Waingarten: Approximating the distance to monotonicity of Boolean functions. In Proc. 31st ACM-SIAM Symp. on Discrete Algorithms (SODA’20), pp. 1995–2009. ACM Press, 2020. [doi:10.1137/1.9781611975994.123, arXiv:1911.06924]

[51]   Michal Parnas, Dana Ron, and Ronitt Rubinfeld: On testing convexity and submodularity. SIAM J. Comput., 32(5):1158–1184, 2003. Preliminary version in RANDOM’02. [doi:10.1137/S0097539702414026]

[52]   Sofya Raskhodnikova: Monotonicity testing. Master’s thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1999. LINK.

[53]   Sofya Raskhodnikova: Property Testing: Theory and Applications. Ph. D. thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2003. LINK.

[54]   Sofya Raskhodnikova: Transitive-closure spanners: A survey. In Property Testing, volume 6390 of LNCS, pp. 167–196. Springer, 2010. [doi:10.1007/978-3-642-16367-8_10]

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

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

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

[58]   Sofya Raskhodnikova and Grigory Yaroslavtsev: Learning pseudo-Boolean k-DNF and submodular functions. In Proc. 24th ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1356–1368. ACM Press, 2013. [doi:10.1137/1.9781611973105.98, arXiv:1208.2294]

[59]   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]

[60]   C. Seshadhri and Jan Vondrák: Is submodularity testable? Algorithmica, 69(1):1–25, 2014. Preliminary version in ICS’10. [doi:10.1007/s00453-012-9719-2, arXiv:1008.0831]

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