License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.29
URN: urn:nbn:de:0030-drops-94338
Go to the corresponding LIPIcs Volume Portal

Babai, László ; Black, Timothy J. F. ; Wuu, Angela

List-Decoding Homomorphism Codes with Arbitrary Codomains

LIPIcs-APPROX-RANDOM-2018-29.pdf (0.6 MB)


The codewords of the homomorphism code aHom(G,H) are the affine homomorphisms between two finite groups, G and H, generalizing Hadamard codes. Following the work of Goldreich-Levin (1989), Grigorescu et al. (2006), Dinur et al. (2008), and Guo and Sudan (2014), we further expand the range of groups for which local list-decoding is possible up to mindist, the minimum distance of the code. In particular, for the first time, we do not require either G or H to be solvable. Specifically, we demonstrate a poly(1/epsilon) bound on the list size, i. e., on the number of codewords within distance (mindist-epsilon) from any received word, when G is either abelian or an alternating group, and H is an arbitrary (finite or infinite) group. We conjecture that a similar bound holds for all finite simple groups as domains; the alternating groups serve as the first test case.
The abelian vs. arbitrary result permits us to adapt previous techniques to obtain efficient local list-decoding for this case. We also obtain efficient local list-decoding for the permutation representations of alternating groups (the codomain is a symmetric group) under the restriction that the domain G=A_n is paired with codomain H=S_m satisfying m < 2^{n-1}/sqrt{n}.
The limitations on the codomain in the latter case arise from severe technical difficulties stemming from the need to solve the homomorphism extension (HomExt) problem in certain cases; these are addressed in a separate paper (Wuu 2018).
We introduce an intermediate "semi-algorithmic" model we call Certificate List-Decoding that bypasses the HomExt bottleneck and works in the alternating vs. arbitrary setting. A certificate list-decoder produces partial homomorphisms that uniquely extend to the homomorphisms in the list. A homomorphism extender applied to a list of certificates yields the desired list.

BibTeX - Entry

  author =	{L{\'a}szl{\'o} Babai and Timothy J. F. Black and Angela Wuu},
  title =	{{List-Decoding Homomorphism Codes with Arbitrary Codomains}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-94338},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.29},
  annote =	{Keywords: Error-correcting codes, Local algorithms, Local list-decoding, Finite groups, Homomorphism codes}

Keywords: Error-correcting codes, Local algorithms, Local list-decoding, Finite groups, Homomorphism codes
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI