Tradeoff between repair bandwidth and sub-packetization for Reed–Solomon codes

About 7 years old · traced to

Let [n,k][n,k] denote a Reed–Solomon code with an ϵ\epsilon-MSR repair scheme, meaning that the repair bandwidth for every single failed node is at most (1+ϵ)(1+\epsilon) times the cut-set bound. The tradeoff conjecture. Any [n,k][n,k] ϵ\epsilon-MSR Reed–Solomon code has sub-packetization (n−k)Ω(1/ϵ)(n-k)^{\Omega(1/\epsilon)}, and this is tight up to a constant factor in the exponent. The paper's constructions achieve polynomial sub-packetization in the constant-rate regime, including (n−k)O(1/ϵ)(n-k)^{O(1/\epsilon)} for its ϵ\epsilon-MSR family; the conjecture asserts that this dependence on ϵ\epsilon is essentially optimal.

References

Primary source

Venkatesan Guruswami and Haotian Jiang, “Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization”, arXiv:1907.03931 (2019).

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.