The fundamental trade-off conjecture for expander-code decoding

Let GG be a (c,d,α,δ)(c,d,\alpha,\delta)-bipartite expander and let C0F2dC_0\subseteq\mathbb{F}_2^d be an inner code with minimum Hamming distance d(C0)d0d(C_0)\ge d_0. Let T(G,C0)F2nT(G,C_0)\subseteq\mathbb{F}_2^n denote the associated expander code. Expander-code trade-off conjecture. If δd0>1\delta d_0>1, then T(G,C0)T(G,C_0) can correct Ωc,d,α,δ(n)\Omega_{c,d,\alpha,\delta}(n) errors in Oc,d,α,δ(n)O_{c,d,\alpha,\delta}(n) time for every such GG and C0C_0. This conjecture would make the necessary condition δd0>1\delta d_0>1 essentially sufficient, improving the paper's sufficient condition δd0>3\delta d_0>3 and identifying the fundamental trade-off between expansion and inner-code distance.

Sources & referencesView supporting material

Primary source

Kuan Cheng, Minghui Ouyang, Chong Shangguan and Yuanting Shen, “When can an expander code correct Ω(n) errors in O(n) time?”, arXiv:2312.16087 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.