Regularity characterization conjecture for correctable patterns in tensor-product topologies

Consider the topology Tm×n(a,b,0)T_{m\times n}(a,b,0) and an erasure pattern E[m]×[n]E\subseteq [m]\times[n]. For all U[m]U\subseteq [m] and V[n]V\subseteq [n], write U=u|U|=u and V=v|V|=v. The pattern EE is regular if

E(U×V)va+ubab.|E\cap (U\times V)|\leq va+ub-ab.

Regularity characterization conjecture. An erasure pattern EE is correctable for Tm×n(a,b,0)T_{m\times n}(a,b,0) if and only if it is regular.

Regularity is known to be necessary for correctability, while the source states that sufficiency is proved in the setting where a=1a=1; the general characterization remains open.

Sources & referencesView supporting material

Primary source

Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang and Sergey Yekhanin, “Maximally Recoverable Codes for Grid-like Topologies”, arXiv:1605.05412 (2016).

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.