Zobrazeno 1 - 10
of 147
pro vyhledávání: '"Samorodnitsky, Alex"'
Autor:
Avni, Amit, Samorodnitsky, Alex
We describe the eigenvalues and the eigenspaces of the adjacency matrices of subgraphs of the Hamming cube induced by Hamming balls, and more generally, by a union of adjacent concentric Hamming spheres. As a corollary, we extend the range of cardina
Externí odkaz:
http://arxiv.org/abs/2411.14597
We consider the problem of discrimination between two pure quantum states. It is well known that the optimal measurement under both the error-probability and log-loss criteria is a projection, while under an ``erasure-distortion'' criterion it is a t
Externí odkaz:
http://arxiv.org/abs/2311.02366
Autor:
Samorodnitsky, Alex
The first linear programming bound of McEliece, Rodemich, Rumsey, and Welch is the best known asymptotic upper bound for binary codes, for a certain subrange of distances. Starting from the work of Friedman and Tillich, there are, by now, some arguab
Externí odkaz:
http://arxiv.org/abs/2308.16038
Autor:
Samorodnitsky, Alex
We describe some pseudorandom properties of binary linear codes achieving capacity on the binary erasure channel under bit-MAP decoding (as shown in Kudekar et al this includes doubly transitive codes and, in particular, Reed-Muller codes). We show t
Externí odkaz:
http://arxiv.org/abs/2206.05135
Autor:
Samorodnitsky, Alex
For $0 < \lambda < 1$ and $n \rightarrow \infty$ pick uniformly at random $\lambda n$ vectors in $\{0,1\}^n$ and let $C$ be the orthogonal complement of their span. Given $0 < \gamma < \frac12$ with $0 < \lambda < h(\gamma)$, let $X$ be the random va
Externí odkaz:
http://arxiv.org/abs/2205.02051
Autor:
Levhari, Niv, Samorodnitsky, Alex
Let $T_{\epsilon}$, $0 \le \epsilon \le 1/2$, be the noise operator acting on functions on the boolean cube $\{0,1\}^n$. Let $f$ be a distribution on $\{0,1\}^n$ and let $q > 1$. We prove tight Mrs. Gerber-type results for the second Renyi entropy of
Externí odkaz:
http://arxiv.org/abs/2112.09039
Autor:
Samorodnitsky, Alex
We give one more proof of the first linear programming bound for binary codes, following the line of work initiated by Friedman and Tillich. The new argument is somewhat similar to previous proofs, but we believe it to be both simpler and more intuit
Externí odkaz:
http://arxiv.org/abs/2104.14587
Autor:
Samorodnitsky, Alex
Let $T_{\epsilon}$, $0 \le \epsilon \le 1/2$, 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$. In arXiv:1809.09696 the $\ell_q$ norm of $T_{\epsilon} f$ was
Externí odkaz:
http://arxiv.org/abs/2010.02721
Autor:
Samorodnitsky, Alex, Sberlo, Ori
Using techniques and results from Kudekar et al. we strengthen the bounds on the weight distribution of linear codes achieving capacity on the BEC, which were shown by the first author. In particular, we show that for any doubly transitive binary lin
Externí odkaz:
http://arxiv.org/abs/2008.07236
Autor:
Kirshner, Naomi, Samorodnitsky, Alex
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 biv
Externí odkaz:
http://arxiv.org/abs/1909.11929