List-Decoding Homomorphism Codes with Arbitrary Codomains

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



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.29.pdf
  • Filesize: 0.55 MB
  • 18 pages

Document Identifiers

Author Details

László Babai
  • University of Chicago, Chicago IL, USA
Timothy J. F. Black
  • University of Chicago, Chicago IL, USA
Angela Wuu
  • University of Chicago, Chicago IL, USA

Cite AsGet BibTex

László Babai, Timothy J. F. Black, and Angela Wuu. List-Decoding Homomorphism Codes with Arbitrary Codomains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.29

Abstract

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Error-correcting codes
  • Local algorithms
  • Local list-decoding
  • Finite groups
  • Homomorphism codes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. László Babai. On the length of subgroup chains in the symmetric group. Communications in Algebra, 14(9):1729-1736, 1986. URL: http://dx.doi.org/10.1080/00927878608823393.
  2. László Babai. Local expansion of vertex-transitive graphs and random generation in finite groups. In 23rd STOC, pages 164-174. ACM, 1991. URL: http://dx.doi.org/10.1145/103418.103440.
  3. László Babai, Robert Beals, and Ákos Seress. Polynomial-time theory of matrix groups. In 41st STOC, pages 55-64. ACM, 2009. URL: http://dx.doi.org/10.1145/1536414.1536425.
  4. László Babai, Timothy J. F. Black, and Angela Wuu. List-decoding homomorphism codes with arbitrary codomains. arXiv, 2018. (full version of this paper). URL: http://arxiv.org/abs/1806.02969.
  5. László Babai and Endre Szemerédi. On the complexity of matrix group problems I. In 25th FOCS, pages 229-240. IEEE Computer Soc., 1984. URL: http://dx.doi.org/10.1109/SFCS.1984.715919.
  6. László Babai. The probability of generating the symmetric group. J. Combinat. Theory, Series A, 52(1):148-153, 1989. URL: http://dx.doi.org/10.1016/0097-3165(89)90068-X.
  7. Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger, and Ákos Seress. Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules. J. Algebra, 292(1):4-46, 2005. URL: http://dx.doi.org/10.1016/j.jalgebra.2005.01.035.
  8. Abhishek Bhowmick and Shachar Lovett. The list decoding radius of Reed-Muller codes over small fields. In 47th STOC, pages 277-285. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746543.
  9. Timothy Black, Alan Guo, Madhu Sudan, and Angela Wuu. List decoding nilpotent groups. In preparation, 2018. Google Scholar
  10. Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Decodability of group homomorphisms beyond the Johnson bound. In 40th STOC, pages 275-284. ACM, 2008. URL: http://dx.doi.org/10.1145/1374376.1374418.
  11. John D. Dixon and Brian Mortimer. Permutation Groups. Graduate Texts in Math. Springer New York, 1996. Google Scholar
  12. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In 21st STOC, pages 25-32. ACM, 1989. URL: http://dx.doi.org/10.1145/73007.73010.
  13. Parikshit Gopalan, Adam R. Klivans, and David Zuckerman. List-decoding Reed-Muller codes over small fields. In 40th STOC, pages 265-274. ACM, 2008. URL: http://dx.doi.org/10.1145/1374376.1374417.
  14. Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Local decoding and testing for homomorphisms. In APPROX-RANDOM, volume 4110 of Lecture Notes in Computer Science, pages 375-385. Springer, 2006. URL: http://dx.doi.org/10.1007/11830924_35.
  15. Alan Guo. Group homomorphisms as error correcting codes. Electronic J. Combinatorics, 22(1):P1.4, 2015. Google Scholar
  16. Alan Guo and Madhu Sudan. List decoding group homomorphisms between supersolvable groups. In APPROX/RANDOM, volume 28 of LIPIcs, pages 737-747. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.737.
  17. William Cary Huffman and Vera Pless. Fundamentals of Error-Correcting Codes. Cambridge Univ. Press, 2003. Google Scholar
  18. I. Martin Isaacs. Finite Group Theory. Graduate studies in mathematics. Amer. Math. Soc., 2008. Google Scholar
  19. Derek J. S. Robinson. A Course in the Theory of Groups. Springer, 2nd edition, 1995. Google Scholar
  20. Ákos Seress. Permutation Group Algorithms. Cambridge Tracts in Math. Cambridge Univ. Press, 2003. Google Scholar
  21. Angela Wuu. Homomorphism extension. arXiv, 2018. URL: http://arxiv.org/abs/1802.08656.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail