Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-28T14:44:25.106Z Has data issue: false hasContentIssue false
  • English
  • Français

Boolean functions with small spectral norm, revisited

Published online by Cambridge University Press:  16 May 2018

TOM SANDERS
TOM SANDERS*
Affiliation:
Mathematical Institute, University of Oxford, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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