Spectral norm of symmetric functions

DOI10.1007/978-3-642-32512-0_29MaRDI QIDQ3167408zbMATH OpenOpenAlexWikidataFDO

Authors Anil Ada, Omar Fawzi, Hamed Hatami

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.5282

Mathematics Subject Classification ID

Boolean functions (06E30) Combinatorics in computer science (68R05)

Abstract: The spectral norm of a Boolean function $f:{0,1}^{n}o-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)cdotparity(x)$ is constant for all $x$ with $sum{x}_{i}in[r_0,n-r_1]$. We mention some applications to the decision tree and communication complexity of symmetric functions.

Recommendations

• Evaluating spectral norms for constant depth circuits with symmetric gates
• A lifting theorem with applications to symmetric functions
• Boolean functions with small spectral norm, revisited

Cited in

(14)

• Spectra with positive elementary symmetric functions
• Spectral properties of threshold functions
• Evaluating spectral norms for constant depth circuits with symmetric gates
• Boolean functions with small spectral norm
• A geometrical representation of the Fourier transformation of Boolean functions
• Complexity theoretic aspects of some cryptographic functions
• Spectral functions of a symmetric linear relation with a directing mapping, I
• Spectral functions of a symmetric linear relation with a directing mapping, II
• scientific article; zbMATH DE number 2114156 (Why is no real title available?)
• scientific article; zbMATH DE number 7561760 (Why is no real title available?)
• A lifting theorem with applications to symmetric functions
• Boolean functions with small spectral norm, revisited
• Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
• scientific article; zbMATH DE number 3101046 (Why is no real title available?)

This page was built for publication: Spectral norm of symmetric functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167408)