License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.60
URN: urn:nbn:de:0030-drops-188858
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18885/
Jeronimo, Fernando Granha
Fast Decoding of Explicit Almost Optimal ε-Balanced q-Ary Codes And Fast Approximation of Expanding k-CSPs
Abstract
Good codes over an alphabet of constant size q can approach but not surpass distance 1-1/q. This makes the use of q-ary 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 1-1/q-ε for small ε > 0, the Gilbert-Varshamov (GV) bound asserts that rate Ω_q(ε²) is achievable whereas the q-ary 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 q-ary 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 (1-1/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 non-zero codeword, the frequency of each symbol lies in the interval [1/q - ε, 1/q + ε]. A key ingredient of the q-ary decoder is a new near-linear time approximation algorithm for linear equations (k-LIN) over ℤ_q on expanding hypergraphs, in particular, those naturally arising in the decoding of these codes.
We also investigate k-CSPs on expanding hypergraphs in more generality. We show that special trade-offs available for k-LIN 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 near-linear time approximation algorithm for general expanding k-CSPs over q-ary 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 Sum-of-Squares 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 k-XOR with the goal of providing near-linear time decoder for explicit binary codes, near the GV bound, from the breakthrough work of Ta-Shma [STOC, 2017]. The explicit families of codes over prime F_q are based on suitable instatiations of the Jalan-Moshkovitz (Abelian) generalization of Ta-Shma’s distance amplification procedure.
BibTeX - Entry
@InProceedings{jeronimo:LIPIcs.APPROX/RANDOM.2023.60,
author = {Jeronimo, Fernando Granha},
title = {{Fast Decoding of Explicit Almost Optimal \epsilon-Balanced q-Ary Codes And Fast Approximation of Expanding k-CSPs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {60:1--60:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-296-9},
ISSN = {1868-8969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18885},
URN = {urn:nbn:de:0030-drops-188858},
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 |
