Article contents
Boolean functions with small spectral norm, revisited
Published online by Cambridge University Press: 16 May 2018
Abstract
We show that if f is a Boolean function on F2n with spectral norm at most M then there is some L ≤ exp(M3+o(1)) and subspaces V1,. . .,VL such that f = Σi ± 1Vi.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 167 , Issue 2 , September 2019 , pp. 335 - 344
- Copyright
- Copyright © Cambridge Philosophical Society 2018
References
REFERENCES
[1] Ada, A., Fawzi, O. and Hatami, H.. Spectral norm of symmetric functions. Approximation, randomisation, and combinatorial optimisation. algorithms and techniques (2012), 338–349.Google Scholar
[2] Croot, E. S., Łaba, I. and Sisask, O.. Arithmetic progressions in sumsets and L p-almost-periodicity (2011).Google Scholar
[3] Green, B. J. and Konyagin, S. V. On the Littlewood problem modulo a prime. Canad. J. Math., 61 (2009), no. 1, 141–164.Google Scholar
[4] Green, B. J. and Sanders, T.. Boolean functions with small spectral norm. Geom. Funct. Anal. 18 (2008), no. 1, 144–162, arXiv:math/0605524.Google Scholar
[5] Green, B. J. and Sanders, T.. A quantitative version of the idempotent theorem in harmonic analysis. Ann. of Math. (2), 168 (2008), no. 3, 1025–1054, arXiv:math/0611286.Google Scholar
[6] Grolmusz, V.. On the power of circuits with gates of low L 1 norms. Theoret. Comput. Sci. 188 (1997), no. 1-2, 117–128.Google Scholar
[7] Kushilevitz, E. and Mansour, Y. Learning decision trees using the fourier spectrum. SIAM Journal on Computing, 22 (1993), no. 6, 1331–1348, https://doi.org/10.1137/0222080.Google Scholar
[8] Mansour, Y.. Learning Boolean functions via the Fourier transform. Theoretical Advances in Neural Computation and Learning. (1994), 391–424.Google Scholar
[9] Méla, J.-F Mesures ϵ-idempotentes de norme bornée. Studia Math., 72 (1982), no. 2, 131–149.Google Scholar
[10] Ruzsa, I. Z. An analog of Freĭman's theorem in groups. Astérisque. 258 (1999), xv, 323–326, Structure theory of set addition.Google Scholar
[11] Sanders, T.. On the Bogolyubov-Ruzsa lemma. Anal. PDE, 5 (2012), no. 3, 627–655, arXiv:1011.0107.Google Scholar
[12] Sanders, T.. The structure theory of set addition revisited. Bull. Amer. Math. Soc. 50 (2013), 93–127, arXiv:1212.0458.Google Scholar
[13] Sanders, T. Bounds in the idempotent theorem. ArXiv e-prints (October 2016), available at 1610.07092,Google Scholar
[14] Shpilka, A., Tal, A. and Volk, B. On the structure of Boolean functions with small spectralnorm. Proceedings of the 5th conference on innovations in theoretical computer science (2014), pp. 37–48.Google Scholar
[15] Tao, T. C. and Vu, H. V. Additive combinatorics. Camb. Stud. Adv. Math., vol. 105 (Cambridge University Press, Cambridge, 2006).Google Scholar
[16] Tsang, H.-Y., Wong, C., Xie, N. and Zhang, S. Fourier sparsity, spectral norm, and the log-rank conjecture, Proceedings of the 2013 ieee 54th annual symposium on foundations of computer science (2013), pp. 658–667.Google Scholar
[17] Zwillinger, D., Krantz, S. G. and Rosen, K. H. (eds.). CRC Standard Mathematical Tables and Formulae, 31st ed. (CRC Press, Boca Raton, FL, 2003).Google Scholar
- 2
- Cited by