[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]   Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu: Estimating the distance to a monotone function. Random Structures Algorithms, 31(3):371–383, 2007. Preliminary version in RANDOM’04. [doi:10.1002/rsa.20167]

[3]   Kazuyuki Amano and Akira Maruoka: A superpolynomial lower bound for a circuit computing the Clique function with at most (1∕6)log log n negation gates. SIAM J. Comput., 35(1):201–216, 2005. Preliminary version in MFCS’98. [doi:10.1137/S0097539701396959]

[4]   Dana Angluin: Queries and concept learning. Machine Learning, 2(4):319–342, 1988. [doi:10.1007/BF00116828]

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

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

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

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

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

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

[11]   Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan: Learning circuits with few negations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM 2015), volume 40, pp. 512–527. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.512, arXiv:1410.8420]

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

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

[14]   Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer: Testing k-monotonicity. In Proc. 8th Symp. Innovations in Theoretical Computer Science (ITCS’17). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.29, arXiv:1609.00265]

[15]   Clément L. Canonne and Ronitt Rubinfeld: Testing probability distributions underlying aggregated data. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), volume 8572 of Lecture Notes in Computer Science, pp. 283–295. Springer, 2014. [doi:10.1007/978-3-662-43948-7_24, arXiv:1402.3835, ECCC:TR14-021]

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

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

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

[19]   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, 2015. [doi:10.1145/2746539.2746570, arXiv:1412.5657]

[20]   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 Computer Society, 2014. [doi:10.1109/FOCS.2014.38, arXiv:1412.5655]

[21]   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, 2017. [doi:10.1145/3055399.3055461, arXiv:1702.06997]

[22]   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), volume 1671 of Lecture Notes in Computer Science, pp. 97–108. Springer, 1999. [doi:10.1007/978-3-540-48413-4_10]

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

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

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

[26]   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, 2002. [doi:10.1145/509907.509977]

[27]   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. 32–42. ACM, 1991. [doi:10.1145/103418.103429]

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

[29]   Elena Grigorescu, Akash Kumar, and Karl Wimmer: Flipping out with many flips: Hardness of testing k-monotonicity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM 2018), pp. 40:1–17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.40]

[30]   Siyao Guo and Ilan Komargodski: Negation-limited formulas. Theoret. Comput. Sci., 660:75–85, 2017. Preliminary version in RANDOM’15. [doi:10.1016/j.tcs.2016.11.027]

[31]   Siyao Guo, Tal Malkin, Igor C. Oliveira, and Alon Rosen: The power of negations in cryptography. In 12th Theory of Cryptography Conf. (TCC’15), volume 9014 of Lecture Notes in Computer Science, pp. 36–65. Springer, 2015. [doi:10.1007/978-3-662-46494-6_3]

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

[33]   Stasys Jukna: Boolean Function Complexity. Springer, 2012. [doi:10.1007/978-3-642-24508-4]

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

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

[36]   Michael J. Kearns and Leslie G. Valiant: Cryptographic limitations on learning Boolean formulae and finite automata. J. ACM, 41(1):67–95, 1994. Preliminary version in STOC’89. [doi:10.1145/174644.174647]

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

[38]   Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell, and Chenggang Wu: Testing surface area. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1204–1214. SIAM, 2014. [doi:10.1137/1.9781611973402.89]

[39]   Chengyu Lin and Shengyu Zhang: Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers. In Proc. 44th Internat. Colloq. on Automata, Languages and Programming (ICALP’17), pp. 51:1–13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ICALP.2017.51, arXiv:1602.06627]

[40]   Andrei A. Markov: On the inversion complexity of systems of functions. Doklady Akademii Nauk SSSR, N.S., 116:917–919, 1957. English translation in [41].

[41]   Andrei A. Markov: On the inversion complexity of a system of functions. J. ACM, 5(4):331–334, 1958. [doi:10.1145/320941.320945]

[42]   Joe Neeman: Testing surface area with arbitrary accuracy. In Proc. 46th STOC, pp. 393–397. ACM, 2014. [doi:10.1145/2591796.2591807]

[43]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge University Press, 2014. [doi:10.1017/CBO9781139814782]

[44]   Ryan O’Donnell and Rocco A. Servedio: Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827–844, 2007. Preliminary version in CCC’06. [doi:10.1137/060669309]

[45]   Ryan O’Donnell and Karl Wimmer: KKL, Kruskal-Katona, and monotone nets. SIAM J. Comput., 42(6):2375–2399, 2013. Preliminary version in FOCS’09. [doi:10.1137/100787325]

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

[47]   Ran Raz and Avi Wigderson: Monotone circuits for matching require linear depth. J. ACM, 39(3):736–744, 1992. Preliminary version in STOC’90. [doi:10.1145/146637.146684]

[48]   Alexander A. Razborov: Lower bounds on the monotone complexity of some Boolean functions. Doklady Akademii Nauk SSSR, N.S., 281(4):798–801, 1985. English translation in Soviet Math. Doklady, 31:354–357, 1985.

[49]   Benjamin Rossman: Correlation bounds against monotone NC¹. In Proc. 30th IEEE Conf. on Computational Complexity (CCC’15), pp. 392–411. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.CCC.2015.392]

[50]   Rocco A. Servedio: On learning monotone DNF under product distributions. Inform. and Comput., 193(1):57–74, 2004. Preliminary version in COLT’01. [doi:10.1016/j.ic.2004.04.003]

[51]   Leslie G. Valiant: A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. Preliminary version in STOC’84. [doi:10.1145/1968.1972]

[52]   Grigory Yaroslavtsev: List of open problems in sublinear algorithms: Problem 70. http://sublinear.info/70, 2016. Originally posed in [8].