Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908483652157440 |
|---|---|
| author | Abawonse, Olakunle S. Hazla, Jan O'Donnell, Ryan |
| author_facet | Abawonse, Olakunle S. Hazla, Jan O'Donnell, Ryan |
| contents | An inequality by Samorodnitsky states that if $f : \mathbb{F}_2^n \to \mathbb{R}$ is a nonnegative boolean function, and $S \subseteq [n]$ is chosen by randomly including each coordinate with probability a certain $λ= λ(q,ρ) < 1$, then \begin{equation}
\log \|T_ρf\|_q \leq \mathbb{E}_{S} \log \|\mathbb{E}(f|S)\|_q\;. \end{equation} Samorodnitsky's inequality has several applications to the theory of error-correcting codes. Perhaps most notably, it can be used to show that \emph{any} binary linear code (with minimum distance $ω(\log n)$) that has vanishing decoding error probability on the BEC$(λ)$ (binary erasure channel) also has vanishing decoding error on \emph{all} memoryless symmetric channels with capacity above some $C = C(λ)$.
Samorodnitsky determined the optimal $λ= λ(q,ρ)$ for his inequality in the case that $q \geq 2$ is an integer. In this work, we generalize the inequality to $f : Ω^n \to \mathbb{R}$ under any product probability distribution $μ^{\otimes n}$ on $Ω^n$; moreover, we determine the optimal value of $λ= λ(q,μ,ρ)$ for any real $q \in [2,\infty]$, $ρ\in [0,1]$, and distribution~$μ$. As one consequence, we obtain the aforementioned coding theory result for linear codes over \emph{any} finite alphabet. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06940 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes Abawonse, Olakunle S. Hazla, Jan O'Donnell, Ryan Information Theory 68P30 (Primary) 68Q30, 94B70 (Secondary) An inequality by Samorodnitsky states that if $f : \mathbb{F}_2^n \to \mathbb{R}$ is a nonnegative boolean function, and $S \subseteq [n]$ is chosen by randomly including each coordinate with probability a certain $λ= λ(q,ρ) < 1$, then \begin{equation} \log \|T_ρf\|_q \leq \mathbb{E}_{S} \log \|\mathbb{E}(f|S)\|_q\;. \end{equation} Samorodnitsky's inequality has several applications to the theory of error-correcting codes. Perhaps most notably, it can be used to show that \emph{any} binary linear code (with minimum distance $ω(\log n)$) that has vanishing decoding error probability on the BEC$(λ)$ (binary erasure channel) also has vanishing decoding error on \emph{all} memoryless symmetric channels with capacity above some $C = C(λ)$. Samorodnitsky determined the optimal $λ= λ(q,ρ)$ for his inequality in the case that $q \geq 2$ is an integer. In this work, we generalize the inequality to $f : Ω^n \to \mathbb{R}$ under any product probability distribution $μ^{\otimes n}$ on $Ω^n$; moreover, we determine the optimal value of $λ= λ(q,μ,ρ)$ for any real $q \in [2,\infty]$, $ρ\in [0,1]$, and distribution~$μ$. As one consequence, we obtain the aforementioned coding theory result for linear codes over \emph{any} finite alphabet. |
| title | Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes |
| topic | Information Theory 68P30 (Primary) 68Q30, 94B70 (Secondary) |
| url | https://arxiv.org/abs/2508.06940 |