The fundamental trade-off conjecture for expander-code decoding
The fundamental trade-off conjecture for expander-code decoding
Let be a -bipartite expander and let be an inner code with minimum Hamming distance . Let denote the associated expander code. Expander-code trade-off conjecture. If , then can correct errors in time for every such and . This conjecture would make the necessary condition essentially sufficient, improving the paper's sufficient condition 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.