Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNCERTAINTY PRINCIPLE:
Reports tagged with Uncertainty principle:
TR12-031 | 4th April 2012
Tom Gur, Omer Tamuz

Testing Booleanity and the Uncertainty Principle

Revisions: 1

Let f:\{-1,1\}^n \to \mathbb{R} be a real function on the hypercube, given
by its discrete Fourier expansion, or, equivalently, represented as
a multilinear polynomial. We say that it is Boolean if its image is
in \{-1,1\}.

We show that every function on the hypercube with a ... more >>>


TR18-016 | 25th January 2018
Naomi Kirshner, Alex Samorodnitsky

On \ell_4 : \ell_2 ratio of functions with restricted Fourier support

Revisions: 1

Given a subset A\subseteq \{0,1\}^n, let \mu(A) be the maximal ratio between \ell_4 and \ell_2 norms of a function whose Fourier support is a subset of A. We make some simple observations about the connections between \mu(A) and the additive properties of A on one hand, and between \mu(A) and ... more >>>




ISSN 1433-8092 | Imprint