Universal combinatorial list-decodability for finite simple groups

Let GG be a finite simple group, let HH be an arbitrary finite or infinite group, and let aHom(G,H)\operatorname{aHom}(G,H) denote the homomorphism code. A class of finite groups is universally CombEcon if, for every group in the class and every such codomain HH, the corresponding homomorphism code is CombEcon; equivalently, for every ε>0\varepsilon>0, every received word has at most poly(1/ε)\operatorname{poly}(1/\varepsilon) codewords within distance mindistε\textsf{mindist}-\varepsilon, where mindist\textsf{mindist} is the code's minimum distance.

Universal finite-simple-group conjecture. The class of finite simple groups is universally CombEcon.

The paper proves this property for finite abelian and alternating groups, identifying the alternating groups as a first test case for the expected general phenomenon among finite simple groups. The conjecture extends the combinatorial list-decoding result to all finite simple domains, while allowing arbitrary codomains.

Sources & referencesView supporting material

Primary source

László Babai, Timothy J. F. Black and Angela Wuu, “List-decoding homomorphism codes with arbitrary codomains”, arXiv:1806.02969 (2018).

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.