Spectral Norm of Symmetric Functions

2012/05/23 by Anil Ada, Omar Fawzi, Ada, Anil +3 · 2 citations
Computer Science · #Coding theory and cryptography #Machine Learning and Algorithms #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1205.5282

Abstract

The spectral norm of a Boolean function f:\0,1\ⁿ → \-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₀,r₁\, and r₀ and r₁ are the smallest integers less than n/2 such that f(x) or f(x) ⋅ parity(x) is constant for all x with ∑ x_i ∈ [r₀, n-r₁]. We mention some applications to the decision tree and communication complexity of symmetric functions.

Cited by

• Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
• Fourier sparsity, spectral norm, and the Log-rank conjecture

Related

• On the Spectral Properties of Symmetric Functions
• On the Structure of Boolean Functions with Small Spectral Norm
• An inequality for the Fourier spectrum of parity decision trees
• Fourier sparsity, spectral norm, and the Log-rank conjecture
• On parity decision trees for Fourier-sparse Boolean functions