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]