Abstract
The spectral norm of a Boolean function f:{0,1}n → { − 1,1} is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as learning theory, circuit complexity, and communication complexity. In this paper, we give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as r(f)log(n/r(f)) where r(f) = max {r 0,r 1}, and r 0 and r 1 are the smallest integers less than n/2 such that f(x) or \(f(x) \cdot \textnormal{\textsc{parity}}(x)\) is constant for all x with ∑ x i ∈ [r 0, n − r 1]. We mention some applications to the decision tree and communication complexity of symmetric functions.
A full version can be found online [1].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ada, A., Fawzi, O., Hatami, H.: Spectral norm of symmetric functions. arXiv:1205.5282 (2012)
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778–797 (2001)
Bruck, J., Smolensky, R.: Polynomial threshold functions, ac0 functions, and spectral norms. SIAM J. Comput. 21(1), 33–42 (1992)
de Wolf, R.: A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions. Quantum Inf. Comput. 8(10), 943–950 (2008)
Goldmann, M., Håstad, J., Razborov, A.A.: Majority gates vs. general weighted threshold gates. Comput. Complex., 277–300 (1992)
Green, B., Sanders, T.: Boolean functions with small spectral norm. Geom. Funct. Anal. 18(1), 144–162 (2008)
Grolmusz, V.: On the power of circuits with gates of low l1 norms. Theor. Comput. Sci. 188(1-2), 117–128 (1997)
Grolmusz, V.: Harmonic analysis, real approximation, and the communication complexity of boolean functions. Algorithmica 23(4), 341–353 (1999)
Kalai, A.T., Klivans, A.R., Mansour, Y., Servedio, R.A.: Agnostically learning halfspaces. SIAM J. Comput. 37(6), 1777–1805 (2008)
Klivans, A.R., Sherstov, A.A.: Lower bounds for agnostic learning via approximate rank. Comput. Complex. 19(4), 581–604 (2010)
Kolountzakis, M.N., Lipton, R.J., Markakis, E., Mehta, A., Vishnoi, N.K.: On the fourier spectrum of symmetric boolean functions. Combinatorica 29(3), 363–387 (2009)
Kushilevitz, E., Mansour, Y.: Learning decision trees using the fourier spectrum. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 455–464. ACM, New York (1991)
Lee, T., Shraibman, A.: Lower bounds in communication complexity, vol. 3. Now Publishers Inc. (2009)
O’Donnell, R., Servedio, R.A.: Extremal properties of polynomial threshold functions. J. Comput. Syst. Sci. 74(3), 298–312 (2008)
O’Donnell, R., Wright, J., Zhou, Y.: The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 330–341. Springer, Heidelberg (2011)
Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 468–474. ACM, New York (1992)
Razborov, A.: Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics 67(1), 145–159 (2003)
Sherstov, A.A.: Approximate inclusion-exclusion for arbitrary symmetric functions. Comput. Complex. 18(2), 219–246 (2009)
Sherstov, A.A.: The pattern matrix method. SIAM J. Comput. 40(6), 1969–2000 (2011)
Shi, Y., Zhang, Z.: Communication complexities of symmetric XOR functions. Quantum Inf. Comput. (available at arXiv:0808.1762) 9, 255–263 (2009)
Shpilka, A., Tal, A.: On the minimal fourier degree of symmetric boolean functions. In: Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC 2011, pp. 200–209. IEEE Computer Society, Washington, DC (2011)
Siu, K.-Y., Bruck, J.: On the power of threshold circuits with small weights. SIAM J. Discrete Math. 4(3), 423–435 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ada, A., Fawzi, O., Hatami, H. (2012). Spectral Norm of Symmetric Functions. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2012 2012. Lecture Notes in Computer Science, vol 7408. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32512-0_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-32512-0_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32511-3
Online ISBN: 978-3-642-32512-0
eBook Packages: Computer ScienceComputer Science (R0)