English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Tanner codes are graph-based linear codes whose parity-check matrices can becharacterized by a bipartite graph $G$ together with an inner code $C_0$.Expander codes are Tanner codes whose defining bipartite graph $G$ has goodexpansion property. The landmark work of Sipser and Spielman showed that everybipartite expander $G$ with expansion ratio $\delta>3/4$ together with aparity-check code defines an expander code which corrects $\Omega(n)$ errors in$O(n)$ time, where $n$ is the code length. Viderman showed that$\delta>2/3-\Omega(1)$ is already sufficient. Our paper is motivated by thefollowing natural and fundamental problem in decoding expander codes:  \textbf{Question:} What are the sufficient and necessary conditions that$\delta$ and $d_0$ should satisfy so that {\it every} bipartite expander $G$with expansion ratio $\delta$ and {\it every} inner code $C_0$ with minimumdistance $d_0$ together define an expander code which corrects $\Omega(n)$errors in $O(n)$ time?  We give a near-optimal solution to the question above, showing that $\deltad_0>3$ is sufficient and $\delta d_0>1$ is necessary. Our result significantlyimproves the previously known result of Dowling and Gao, who showed that$d_0=\Omega(c\delta^{-2})$ is sufficient, where $c$ is the left-degree of $G$.We suspect that $\delta d_0>1$ is also sufficient to solve the question above.

Improved decoding of expander codes: fundamental trade-off between expansion ratio and minimum distance of inner code