Abstract
Good codes over an alphabet of constant size q can approach but not surpass distance 11/q. This makes the use of qary codes a necessity in some applications, and much work has been devoted to the case of constant alphabet q. In the large distance regime, namely, distance 11/qε for small ε > 0, the GilbertVarshamov (GV) bound asserts that rate Ω_q(ε²) is achievable whereas the qary MRRW bound gives a rate upper bound of O_q(ε²log(1/ε)). In this sense, the GV bound is almost optimal in this regime. Prior to this work there was no known explicit and efficiently decodable qary codes near the GV bound, in this large distance regime, for any constant q ≥ 3.
We design an Õ_{ε,q}(N) time decoder for explicit (expander based) families of linear codes C_{N,q,ε} ⊆ F_q^N of distance (11/q)(1ε) and rate Ω_q(ε^{2+o(1)}), for any desired ε > 0 and any constant prime q, namely, almost optimal in this regime. These codes are εbalanced,i.e., for every nonzero codeword, the frequency of each symbol lies in the interval [1/q  ε, 1/q + ε]. A key ingredient of the qary decoder is a new nearlinear time approximation algorithm for linear equations (kLIN) over ℤ_q on expanding hypergraphs, in particular, those naturally arising in the decoding of these codes.
We also investigate kCSPs on expanding hypergraphs in more generality. We show that special tradeoffs available for kLIN over ℤ_q hold for linear equations over a finite group. To handle general finite groups, we design a new matrix version of weak regularity for expanding hypergraphs. We also obtain a nearlinear time approximation algorithm for general expanding kCSPs over qary alphabet. This later algorithm runs in time Õ_{k,q}(m + n), where m is the number of constraints and n is the number of variables. This improves the previous best running time of O(n^{Θ_{k,q}(1)}) by a SumofSquares based algorithm of [AJT, 2019] (in the expanding regular case).
We obtain our results by generalizing the framework of [JST, 2021] based on weak regularity decomposition for expanding hypergraphs. This framework was originally designed for binary kXOR with the goal of providing nearlinear time decoder for explicit binary codes, near the GV bound, from the breakthrough work of TaShma [STOC, 2017]. The explicit families of codes over prime F_q are based on suitable instatiations of the JalanMoshkovitz (Abelian) generalization of TaShma’s distance amplification procedure.
BibTeX  Entry
@InProceedings{jeronimo:LIPIcs.APPROX/RANDOM.2023.60,
author = {Jeronimo, Fernando Granha},
title = {{Fast Decoding of Explicit Almost Optimal \epsilonBalanced qAry Codes And Fast Approximation of Expanding kCSPs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {60:160:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18885},
URN = {urn:nbn:de:0030drops188858},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.60},
annote = {Keywords: Decoding, Approximation, GV bound, CSPs, HDXs, Regularity}
}
Keywords: 

Decoding, Approximation, GV bound, CSPs, HDXs, Regularity 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 