Sep 16, 2024 · Abstract:The sum of the absolute values of the Fourier coefficients of a function f:\mathbb{F}_2^n \to \mathbb{R} is called the spectral ...

Mar 23, 2022 · The sum of the absolute values of the Fourier coefficients of a function f:Fn2 R is called the spectral norm of f.

Sep 18, 2024 · Of particular relevance to this paper is results about functions that take values in {0,1}, and what it says about such a function if its ...

These studies are often motivated by the existence of efficient learning algorithms for the classes of Boolean functions that have small algebra norms [KM93].

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$.

Aug 4, 2023 · Our main result is an efficient two-party communication protocol for testing linear isomorphism in terms of the approximate spectral norm of the functions.

Sep 20, 2024 · PDF | The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm ...

Abstract. In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is k ˆfk1 = Pα | ˆf(α)|).

May 16, 2018 · 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 ...

Can any function with small spectral norm or small sparsity be represented ... T-approximates and can be learned efficiently. 5. All of the above: also ...