Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SPECTRAL NORM:
Reports tagged with Spectral Norm:
TR13-049 | 1st April 2013
Amir Shpilka, Ben Lee Volk, Avishay Tal

#### On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.

1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.

2. ... more >>>

TR16-093 | 4th June 2016
Cyrus Rashtchian

#### Bounded Matrix Rigidity and John's Theorem

Using John's Theorem, we prove a lower bound on the bounded rigidity of a sign matrix, defined as the Hamming distance between this matrix and the set of low-rank, real-valued matrices with entries bounded in absolute value. For Hadamard matrices, our asymptotic leading constant is tighter than known results by ... more >>>

TR22-041 | 23rd March 2022
Tsun-Ming Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein

#### Boolean functions with small approximate spectral norm

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$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of ... more >>>

ISSN 1433-8092 | Imprint