Simple Codes and Sparse Recovery with Fast Decoding. Cheraghchi, M. & Ribeiro, J. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 156–160, 2019. Link Paper doi abstract bibtex Construction of error-correcting codes achieving a designated minimum distance parameter is a central problem in coding theory. A classical and algebraic family of error-correcting codes studied for this purpose are the BCH codes. In this work, we study a very simple construction of linear codes that achieve a given distance parameter $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 distance parameter $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 non-adaptive 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$.
@INPROCEEDINGS{ref:CR19b,
author = {Mahdi Cheraghchi and Jo\~{a}o Ribeiro},
title = {Simple Codes and Sparse Recovery with Fast Decoding},
year = 2019,
doi = {10.1109/ISIT.2019.8849702},
booktitle = {Proceedings of the {IEEE International Symposium on
Information Theory (ISIT)}},
pages = {156--160},
url_Link = {https://ieeexplore.ieee.org/document/8849702},
url_Paper = {https://arxiv.org/abs/1901.02852},
abstract = {Construction of error-correcting codes achieving a
designated minimum distance parameter is a central
problem in coding theory. A classical and algebraic
family of error-correcting codes studied for this
purpose are the BCH codes. In this work, we study a
very simple construction of linear codes that
achieve a given distance parameter $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 distance parameter $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 non-adaptive
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":"DeSJL2Pp6QXJNd7C4","bibbaseid":"cheraghchi-ribeiro-simplecodesandsparserecoverywithfastdecoding-2019","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M.","Ribeiro, J."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["João"],"propositions":[],"lastnames":["Ribeiro"],"suffixes":[]}],"title":"Simple Codes and Sparse Recovery with Fast Decoding","year":"2019","doi":"10.1109/ISIT.2019.8849702","booktitle":"Proceedings of the IEEE International Symposium on Information Theory (ISIT)","pages":"156–160","url_link":"https://ieeexplore.ieee.org/document/8849702","url_paper":"https://arxiv.org/abs/1901.02852","abstract":"Construction of error-correcting codes achieving a designated minimum distance parameter is a central problem in coding theory. A classical and algebraic family of error-correcting codes studied for this purpose are the BCH codes. In this work, we study a very simple construction of linear codes that achieve a given distance parameter $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 distance parameter $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 non-adaptive 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":"@INPROCEEDINGS{ref:CR19b,\n author =\t {Mahdi Cheraghchi and Jo\\~{a}o Ribeiro},\n title =\t {Simple Codes and Sparse Recovery with Fast Decoding},\n year =\t 2019,\n doi =\t\t {10.1109/ISIT.2019.8849702},\n booktitle =\t {Proceedings of the {IEEE International Symposium on\n Information Theory (ISIT)}},\n pages =\t {156--160},\n url_Link =\t {https://ieeexplore.ieee.org/document/8849702},\n url_Paper =\t {https://arxiv.org/abs/1901.02852},\n abstract =\t {Construction of error-correcting codes achieving a\n designated minimum distance parameter is a central\n problem in coding theory. A classical and algebraic\n family of error-correcting codes studied for this\n purpose are the BCH codes. In this work, we study a\n very simple construction of linear codes that\n achieve a given distance parameter $K$. Moreover, we\n design a simple, nearly optimal syndrome decoder for\n the code as well. The running time of the decoder is\n only logarithmic in the block length of the code,\n and nearly linear in the distance parameter $K$.\n This decoder can be applied to exact for-all sparse\n recovery over any field, improving upon previous\n results with the same number of measurements.\n Furthermore, computation of the syndrome from a\n received word can be done in nearly linear time in\n the block length. We also demonstrate an\n application of these techniques in non-adaptive\n group testing, and construct simple explicit\n measurement schemes with $O(K^2 \\log^2 N)$ tests and\n $O(K^3 \\log^2 N)$ recovery time for identifying up\n to $K$ defectives in a population of size $N$. }\n}\n\n","author_short":["Cheraghchi, M.","Ribeiro, J."],"key":"ref:CR19b","id":"ref:CR19b","bibbaseid":"cheraghchi-ribeiro-simplecodesandsparserecoverywithfastdecoding-2019","role":"author","urls":{" link":"https://ieeexplore.ieee.org/document/8849702"," paper":"https://arxiv.org/abs/1901.02852"},"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-28T19:04:45.014Z","downloads":7,"keywords":[],"search_terms":["simple","codes","sparse","recovery","fast","decoding","cheraghchi","ribeiro"],"title":"Simple Codes and Sparse Recovery with Fast Decoding","year":2019,"dataSources":["YZqdBBx6FeYmvQE6D"]}