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

__
TR18-168
| 25th September 2018
__

Alex Samorodnitsky#### An upper bound on $\ell_q$ norms of noisy functions

__
TR18-023
| 4th February 2018
__

Eran Iceland, Alex Samorodnitsky#### On coset leader graphs of structured linear codes

Revisions: 1

__
TR18-016
| 25th January 2018
__

Naomi Kirshner, Alex Samorodnitsky#### On $\ell_4$ : $\ell_2$ ratio of functions with restricted Fourier support

Revisions: 1

__
TR15-129
| 7th August 2015
__

Alex Samorodnitsky#### On the entropy of a noisy function

Revisions: 1

__
TR14-172
| 12th December 2014
__

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin#### Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

__
TR10-120
| 27th July 2010
__

Noa Eidelstein, Alex Samorodnitsky#### Lower bounds for designs in symmetric spaces

Naomi Kirshner, Alex Samorodnitsky

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 >>>

Alex Samorodnitsky

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 >>>

Eran Iceland, Alex Samorodnitsky

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 >>>

Naomi Kirshner, Alex Samorodnitsky

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 >>>

Alex Samorodnitsky

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 >>>

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

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 >>>

Noa Eidelstein, Alex Samorodnitsky

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 >>>