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

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

[3]   Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang: Active property testing. In Proc. 53rd FOCS, pp. 21–30. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.64]

[4]   Aleksandrs Belovs and Eric Blais: A polynomial lower bound for testing monotonicity. SIAM J. Comput., 50(3):406–433, 2021. Preliminary version in STOC’16. [doi:10.1137/16M1097006]

[5]   Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova: The power and limitations of uniform samples in testing properties of figures. Algorithmica, 81(3):1247–1266, 2019. [doi:10.1007/s00453-018-0467-9]

[6]   Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova: Testing convexity of figures under the uniform distribution. Random Struct. Algor., 54(3):413–443, 2019. [doi:10.1002/rsa.20797]

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

[8]   Arnab Bhattacharyya: A note on the distance to monotonicity of Boolean functions. Electron. Colloq. Comput. Complexity, TR08-012, 2008. [ECCC]

[9]   Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyoming Jung, Sofya Raskhodnikova, and David P. Woodruff: Lower bounds for local monotonicity reconstruction from transitive-closure spanners. SIAM J. Discr. Math., 26(2):618–646, 2012. [doi:10.1137/100808186]

[10]   Hadley Black: Nearly optimal bounds for sample-based testing and learning of k-monotone functions. In Proc. 28th Internat. Conf. on Randomization and Computation (RANDOM’24), pp. 37:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2024. [doi:10.4230/LIPIcs.APPROX/RANDOM.2024.37]

[11]   Hadley Black, Eric Blais, and Nathaniel Harms: Testing and learning convex sets in the ternary hypercube. In Proc. 15th Innovations in Theoret. Comp. Sci. Conf. (ITCS’24), pp. 15:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2024. [doi:10.4230/LIPICS.ITCS.2024.15]

[12]   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 Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’18), pp. 2133–2151. SIAM, 2018. [doi:10.1137/1.9781611975031.139]

[13]   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 Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’20), pp. 1975–1994. SIAM, 2020. [doi:10.1137/1.9781611975994.122]

[14]   Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri: Directed isoperimetric theorems for Boolean functions on the hypergrid and an (n) monotonicity tester. In Proc. 55th STOC, pp. 233–241. ACM Press, 2023. [doi:10.1145/3564246.3585167]

[15]   Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri: A d^1∕2+o(1) monotonicity tester for Boolean functions on d-dimensional hypergrids. SIAM J. Comput., 55(3):147–191, 2026. Preliminary version in FOCS’23. [doi:10.1137/24M163339X]

[16]   Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova: Isoperimetric inequalities for real-valued functions with applications to monotonicity testing. Random Struct. Algor., 65(1):191–219, 2024. [doi:10.1002/rsa.21211]

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

[18]   Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan: Learning circuits with few negations. In Proc. 19th Internat. Workshop on Randomization and Computation (RANDOM’15), pp. 512–527. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.512]

[19]   Eric Blais, Renato Ferreira Pinto Jr, and Nathaniel Harms: VC dimension and distribution-free sample-based testing. In Proc. 53rd STOC, pp. 504–517. ACM Press, 2021. [doi:10.1145/3406325.3451104]

[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]   Eric Blais and Yuichi Yoshida: A characterization of constant-sample testable properties. Random Struct. Algor., 55(1):73–88, 2019. [doi:10.1002/rsa.20807]

[22]   Mark Braverman, Subhash Khot, Guy Kindler, and Dor Minzer: Improved monotonicity testers via hypercube embeddings. In Proc. 14th Innovations in Theoret. Comp. Sci. Conf. (ITCS’23), pp. 25:1–24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2023. [doi:10.4230/LIPIcs.ITCS.2023.25]

[23]   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. [doi:10.1007/s00493-012-2765-1]

[24]   Nader H. Bshouty and Christino Tamon: On the Fourier spectrum of monotone functions. J. ACM, 43(4):747–770, 1996. [doi:10.1145/234533.234564]

[25]   Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer: Testing k-monotonicity: The rise and fall of Boolean functions. Theory of Computing, 15(1):1–55, 2019. [doi:10.4086/toc.2019.v015a001]

[26]   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. Preliminary version in SODA’15. [doi:10.1145/3039241]

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

[28]   Deeparnab Chakrabarty and C. Seshadhri: An o(n) monotonicity tester for Boolean functions over the hypercube. SIAM J. Comput., 45(2):461–472, 2014. [doi:10.1137/13092770X]

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

[30]   Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell: Boolean function monotonicity testing requires (almost) n^1∕2 queries. In Proc. 58th STOC, pp. 584–594. ACM Press, 2026. [doi:10.1145/3798129.3800775, arXiv:2511.04558]

[31]   Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio: Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas. In Proc. 35th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’24), pp. 4321–4337. SIAM, 2024. [doi:10.1137/1.9781611977912.151]

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

[33]   Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun: Sample-based high-dimensional convexity testing. In Proc. 20th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’17), pp. 37:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPICS.APPROX-RANDOM.2017.37]

[34]   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., 2014. [doi:10.1109/FOCS.2014.38]

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

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

[37]   Funda Ergun, 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]

[38]   Shahar Fattal and Dana Ron: Approximating the distance to monotonicity in high dimensions. ACM Trans. Algorithms, 6(3):52:1–37, 2010. [doi:10.1145/1798596.1798605]

[39]   Renato Ferreira Pinto Jr. and Nathaniel Harms: Distribution testing under the parity trace, 2023. [arXiv:2304.01374]

[40]   Renato Ferreira Pinto Jr. and Nathaniel Harms: Distribution testing with a confused collector. In Proc. 15th Innovations in Theoret. Comp. Sci. Conf. (ITCS’24), pp. 47:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2024. [doi:10.4230/LIPICS.ITCS.2024.47]

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

[42]   Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish: Partial tests, universal tests and decomposability. In Proc. 5th Innovations in Theoret. Comp. Sci. Conf. (ITCS’14), pp. 483–500. ACM Press, 2014. [doi:10.1145/2554797.2554841]

[43]   Eldar Fischer, Oded Lachish, and Yadu Vasudev: Trading query complexity for sample-based testing and multi-testing scalability. In Proc. 56th FOCS, pp. 1163–1182. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.75]

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

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

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

[47]   Oded Goldreich and Dana Ron: On sample-based testers. ACM Trans. Comput. Theory, 8(2):7:1–54, 2016. [doi:10.1145/2898355]

[48]   Elena Grigorescu, Akash Kumar, and Karl Wimmer: Flipping out with many flips: Hardness of testing k-monotonicity. SIAM J. Discr. Math., 33(4):2111–2125, 2019. [doi:10.1137/18M1217978]

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

[50]   Shirley Halevy and Eyal Kushilevitz: Testing monotonicity over graph products. Random Struct. Algor., 33(1):44–67, 2008. [doi:10.1002/rsa.20211]

[51]   Nathaniel Harms and Yuichi Yoshida: Downsampling for testing and learning in product distributions. In Proc. 49th Internat. Colloq. on Automata, Languages, and Programming (ICALP’22), pp. 71:1–19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2022. [doi:10.4230/LIPIcs.ICALP.2022.71]

[52]   Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio: Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777–1805, 2008. [doi:10.1137/060649057]

[53]   Michael J. Kearns and Dana Ron: Testing problems with sublearning sample complexity. J. Comput. System Sci., 61(3):428–456, 2000. [doi:10.1006/jcss.1999.1656]

[54]   Subhash Khot, Dor Minzer, and Muli Safra: On monotonicity testing and Boolean isoperimetric type theorems. In Proc. 56th FOCS, pp. 52–58. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.13]

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

[56]   Jane Lange, Ronitt Rubinfeld, and Arsen Vasilyan: Properly learning monotone functions via local correction. In Proc. 63rd FOCS, pp. 75–86. IEEE Comp. Soc., 2022. [doi:10.1109/FOCS54457.2022.00015]

[57]   Jane Lange and Arsen Vasilyan: Agnostic proper learning of monotone functions: Beyond the black-box correction barrier. SIAM J. Comput., 55(3):1–32, 2026. Preliminary version in FOCS’23. [doi:10.1137/24M1630463]

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

[59]   Nathan Linial, Yishay Mansour, and Noam Nisan: Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607–620, 1993. [doi:10.1145/174130.174138]

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

[61]   Sofya Raskhodnikova: Monotonicity testing. Master’s thesis, MIT, 1999. Available at MIT.

[62]   Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, and Omri Weinstein: Approximating the influence of monotone Boolean functions in O() query complexity. ACM Trans. Comput. Theory, 4(4):11:1–12, 2012. Preliminary version in RANDOM’11. [doi:10.1145/2382559.2382562]

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

[64]   Michael E. Saks and C. Seshadhri: Local monotonicity reconstruction. SIAM J. Comput., 39(7):2897–2926, 2010. Preliminary version in SODA’08/ACM DL. [doi:10.1137/080728561]

[65]   Michel Talagrand: How much are increasing sets positively correlated? Combinatorica, 16(2):243–258, 1996. [doi:10.1007/BF01844850]