A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
by Daniel Kane
Theory of Computing, Volume 9(17), pp. 587-592, 2013
Bibliography with links to cited articles
[1] Open Problems in Analysis of Boolean Functions, Compiled for the Simons Symposium, February 5-11, 2012. Technical report, 2012. [arXiv:1204.6447]
[2] Ehud Friedgut: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998. [doi:10.1007/PL00009809]
[3] 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]
[4] Michel Talagrand: How much are increasing sets positively correlated? Combinatorica, 16(2):243–258, 1996. [doi:10.1007/BF01844850]