Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Naomi Kirshner:

TR19-130 | 26th September 2019
Naomi Kirshner, Alex Samorodnitsky

A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres

Let $p \ge 2$. We improve the bound $\frac{\|f\|_p}{\|f\|_2} \le (p-1)^{s/2}$ for a polynomial $f$ of degree $s$ on the boolean cube $\{0,1\}^n$, which comes from hypercontractivity, replacing the right hand side of this inequality by an explicit bivariate function of $p$ and $s$, which is smaller than $(p-1)^{s/2}$ for ... 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