Simple Codes and Sparse Recovery with Fast Decoding. Cheraghchi, M. & Ribeiro, J. SIAM Journal on Discrete Mathematics, 37(2):612-631, 2023. ![Simple Codes and Sparse Recovery with Fast Decoding [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex 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(K^2 łog^2 N)$ tests and $O(K^3 łog^2 N)$ recovery time for identifying up to $K$ defectives in a population of size $N$.
@article{ref:CR23,
author = {Cheraghchi, Mahdi and Ribeiro, Jo\~{a}o},
title = {Simple Codes and Sparse Recovery with Fast Decoding},
journal = {SIAM Journal on Discrete Mathematics},
volume = {37},
number = {2},
pages = {612-631},
year = {2023},
doi = {10.1137/21M1465354},
URL = {https://doi.org/10.1137/21M1465354},
eprint = {https://doi.org/10.1137/21M1465354},
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(K^2 \log^2 N)$ tests and $O(K^3 \log^2 N)$ recovery time for identifying up to $K$ defectives in a population of size $N$.}
}
Downloads: 0
{"_id":"umc7myRRXG6Sz7hbQ","bibbaseid":"cheraghchi-ribeiro-simplecodesandsparserecoverywithfastdecoding-2023","author_short":["Cheraghchi, M.","Ribeiro, J."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Cheraghchi"],"firstnames":["Mahdi"],"suffixes":[]},{"propositions":[],"lastnames":["Ribeiro"],"firstnames":["João"],"suffixes":[]}],"title":"Simple Codes and Sparse Recovery with Fast Decoding","journal":"SIAM Journal on Discrete Mathematics","volume":"37","number":"2","pages":"612-631","year":"2023","doi":"10.1137/21M1465354","url":"https://doi.org/10.1137/21M1465354","eprint":"https://doi.org/10.1137/21M1465354","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(K^2 łog^2 N)$ tests and $O(K^3 łog^2 N)$ recovery time for identifying up to $K$ defectives in a population of size $N$.","bibtex":"@article{ref:CR23,\nauthor = {Cheraghchi, Mahdi and Ribeiro, Jo\\~{a}o},\ntitle = {Simple Codes and Sparse Recovery with Fast Decoding},\njournal = {SIAM Journal on Discrete Mathematics},\nvolume = {37},\nnumber = {2},\npages = {612-631},\nyear = {2023},\ndoi = {10.1137/21M1465354},\nURL = {https://doi.org/10.1137/21M1465354},\neprint = {https://doi.org/10.1137/21M1465354},\nabstract = {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(K^2 \\log^2 N)$ tests and $O(K^3 \\log^2 N)$ recovery time for identifying up to $K$ defectives in a population of size $N$.}\n}\n\n","author_short":["Cheraghchi, M.","Ribeiro, J."],"key":"ref:CR23","id":"ref:CR23","bibbaseid":"cheraghchi-ribeiro-simplecodesandsparserecoverywithfastdecoding-2023","role":"author","urls":{"Paper":"https://doi.org/10.1137/21M1465354"},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"http://mahdi.ch/writings/cheraghchi.bib","dataSources":["YZqdBBx6FeYmvQE6D"],"keywords":[],"search_terms":["simple","codes","sparse","recovery","fast","decoding","cheraghchi","ribeiro"],"title":"Simple Codes and Sparse Recovery with Fast Decoding","year":2023,"downloads":9}