@article{f6e0843a1c3c462698eb82b0704f7d43,
title = "Simple Codes and Sparse Recovery with Fast Decoding",
abstract = "Construction of error-correcting codes achieving a designated minimum distance parameter is a central problem in coding theory. In this work, we study a very simple construction of binary linear codes that correct a given number of errors K. Moreover, we design a simple, nearly optimal syndrome decoder for the code as well. The running time of the decoder is only logarithmic in the block length of the code and nearly linear in the number of errors K. This decoder can be applied to exact for-all sparse recovery over any field, improving upon previous results with the same number of measurements. Furthermore, computation of the syndrome from a received word can be done in nearly linear time in the block length. We also demonstrate an application of these techniques in nonadaptive group testing and construct simple explicit measurement schemes with O(K2 log2 N) tests and O(K3 log2 N) recovery time for identifying up to K defectives in a population of size N.",
keywords = "group testing, sparse recovery, sublinear-time algorithms, syndrome decoding",
author = "Mahdi Cheraghchi and Jo{\~a}o Ribeiro",
note = "Funding Information: *Received by the editors December 14, 2021; accepted for publication (in revised form) November 10, 2022; published electronically May 18, 2023. https://doi.org/10.1137/21M1465354 Funding: The first author's research was partially supported by the National Science Foundation under grants CCF-2006455 and CCF-2107345. The second author's research was partially supported by NSF grants CCF-1814603 and CCF-2107347, NSF award 1916939, the DARPA SIEVE program, a gift from Ripple, a DoE NETL award, a JPMorgan Faculty Fellowship, a PNC center for financial services innovation award, and a CyLab seed funding award. This work was performed while J. Ribeiro was with the Computer Science Department, Carnegie Mellon University, USA, and the Department of Computing, Imperial College London, UK. This work was also mainly performed while M. Cheraghchi was with the Department of Computing, Imperial College London, UK. A shortened version of this work was presented at the 2019 IEEE International Symposium on Information Theory. Funding Information: The first author's research was partially supported by the National Science Foundation under grants CCF-2006455 and CCF-2107345. The second author's research was partially supported by NSF grants CCF-1814603 and CCF-2107347, NSF award 1916939, the DARPA SIEVE program, a gift from Ripple, a DoE NETL award, a JPMorgan Faculty Fellowship, a PNC center for financial services innovation award, and a CyLab seed funding award. This work was performed while J. Ribeiro was with the Computer Science Department, Carnegie Mellon University, USA, and the Department of Computing, Imperial College London, UK. This work was also mainly performed while M. Cheraghchi was with the Department of Computing, Imperial College London, UK. A shortened version of this work was presented at the 2019 IEEE International Symposium on Information Theory. Publisher Copyright: Copyright {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited.",
year = "2023",
doi = "10.1137/21M1465354",
language = "English",
volume = "37",
pages = "612--631",
journal = "Siam Journal On Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics",
number = "2",
}