Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alex Samorodnitsky:

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-168 | 25th September 2018
Alex Samorodnitsky

An upper bound on $\ell_q$ norms of noisy functions

Revisions: 1

Let $T_{\epsilon}$ be the noise operator acting on functions on the boolean cube $\{0,1\}^n$. Let $f$ be a nonnegative function on $\{0,1\}^n$ and let $q \ge 1$. We upper bound the $\ell_q$ norm of $T_{\epsilon} f$ by the average $\ell_q$ norm of conditional expectations of $f$, given sets of roughly ... more >>>

TR18-023 | 4th February 2018
Eran Iceland, Alex Samorodnitsky

On coset leader graphs of structured linear codes

Revisions: 1

We suggest a new approach to obtain bounds on locally correctable and some locally testable binary linear codes, by arguing that their coset leader graphs have high discrete Ricci curvature.

The bounds we obtain for locally correctable codes are worse than the best known bounds obtained using quantum information theory, ... 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 >>>

TR15-129 | 7th August 2015
Alex Samorodnitsky

On the entropy of a noisy function

Revisions: 1

Let $f$ be a nonnegative function on $\{0,1\}^n$. We upper bound the entropy of the image of $f$ under the noise operator with noise parameter $\epsilon$ by the average entropy of conditional expectations of $f$, given sets of roughly $(1-2\epsilon)^2 \cdot n$ variables.

As an application, we show that for ... more >>>

TR14-172 | 12th December 2014
Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

A square matrix $V$ is called rigid if every matrix $V^\prime$ obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major ... more >>>

TR10-120 | 27th July 2010
Noa Eidelstein, Alex Samorodnitsky

Lower bounds for designs in symmetric spaces

A design is a finite set of points in a space on which every "simple" functions averages to its global mean. Illustrative examples of simple functions are low-degree polynomials on the Euclidean sphere or on the Hamming cube.

We prove lower bounds on designs in spaces with a large group ... more >>>

ISSN 1433-8092 | Imprint