Computational Hardness and Explicit Constructions of Error Correcting Codes. Cheraghchi, M., Shokrollahi, A., & Wigderson, A. In Proceedings of the 44th Annual Allerton Conference on Communication, Control, and Computing, pages 1173–1179, 2006. Paper abstract bibtex We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions. Specifically, we give a polynomial time algorithm, which for every integers $n$ and $k$, constructs polynomially many linear codes of block length $n$ and dimension $k$, most of which achieving the Gilbert-Varshamov bound. The success of the procedure relies on the assumption that the exponential time class of $\mathrm{E} := \mathrm{DTIME}[2^{O(n)}]$ is not contained in the sub-exponential space class $\mathrm{DSPACE}[2^{o(n)}]$. The methods used in this paper are by now standard within computational complexity theory, and the main contribution of this note is observing that they are relevant to the construction of optimal codes. We attempt to make this note self contained, and describe the relevant results and proofs from the theory of pseudorandomness in some detail.
@INPROCEEDINGS{ref:conf:CSW06,
author = {Mahdi Cheraghchi and Amin Shokrollahi and Avi
Wigderson},
title = {Computational Hardness and Explicit Constructions of
Error Correcting Codes},
year = 2006,
booktitle = {Proceedings of the 44th {Annual Allerton Conference
on Communication, Control, and Computing}},
pages = {1173--1179},
url_Paper = {https://infoscience.epfl.ch/record/101078},
abstract = { We outline a procedure for using pseudorandom
generators to construct binary codes with good
properties, assuming the existence of sufficiently
hard functions. Specifically, we give a polynomial
time algorithm, which for every integers $n$ and
$k$, constructs polynomially many linear codes of
block length $n$ and dimension $k$, most of which
achieving the Gilbert-Varshamov bound. The success
of the procedure relies on the assumption that the
exponential time class of $\mathrm{E} :=
\mathrm{DTIME}[2^{O(n)}]$ is not contained in the
sub-exponential space class
$\mathrm{DSPACE}[2^{o(n)}]$. The methods used in
this paper are by now standard within computational
complexity theory, and the main contribution of this
note is observing that they are relevant to the
construction of optimal codes. We attempt to make
this note self contained, and describe the relevant
results and proofs from the theory of
pseudorandomness in some detail. }
}
Downloads: 0
{"_id":"42rGTtxnuodZ7yWSe","bibbaseid":"cheraghchi-shokrollahi-wigderson-computationalhardnessandexplicitconstructionsoferrorcorrectingcodes-2006","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","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.","Shokrollahi, A.","Wigderson, A."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Amin"],"propositions":[],"lastnames":["Shokrollahi"],"suffixes":[]},{"firstnames":["Avi"],"propositions":[],"lastnames":["Wigderson"],"suffixes":[]}],"title":"Computational Hardness and Explicit Constructions of Error Correcting Codes","year":"2006","booktitle":"Proceedings of the 44th Annual Allerton Conference on Communication, Control, and Computing","pages":"1173–1179","url_paper":"https://infoscience.epfl.ch/record/101078","abstract":"We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions. Specifically, we give a polynomial time algorithm, which for every integers $n$ and $k$, constructs polynomially many linear codes of block length $n$ and dimension $k$, most of which achieving the Gilbert-Varshamov bound. The success of the procedure relies on the assumption that the exponential time class of $\\mathrm{E} := \\mathrm{DTIME}[2^{O(n)}]$ is not contained in the sub-exponential space class $\\mathrm{DSPACE}[2^{o(n)}]$. The methods used in this paper are by now standard within computational complexity theory, and the main contribution of this note is observing that they are relevant to the construction of optimal codes. We attempt to make this note self contained, and describe the relevant results and proofs from the theory of pseudorandomness in some detail. ","bibtex":"@INPROCEEDINGS{ref:conf:CSW06,\n author =\t {Mahdi Cheraghchi and Amin Shokrollahi and Avi\n Wigderson},\n title =\t {Computational Hardness and Explicit Constructions of\n Error Correcting Codes},\n year =\t 2006,\n booktitle =\t {Proceedings of the 44th {Annual Allerton Conference\n on Communication, Control, and Computing}},\n pages =\t {1173--1179},\n url_Paper =\t {https://infoscience.epfl.ch/record/101078},\n abstract =\t { We outline a procedure for using pseudorandom\n generators to construct binary codes with good\n properties, assuming the existence of sufficiently\n hard functions. Specifically, we give a polynomial\n time algorithm, which for every integers $n$ and\n $k$, constructs polynomially many linear codes of\n block length $n$ and dimension $k$, most of which\n achieving the Gilbert-Varshamov bound. The success\n of the procedure relies on the assumption that the\n exponential time class of $\\mathrm{E} :=\n \\mathrm{DTIME}[2^{O(n)}]$ is not contained in the\n sub-exponential space class\n $\\mathrm{DSPACE}[2^{o(n)}]$. The methods used in\n this paper are by now standard within computational\n complexity theory, and the main contribution of this\n note is observing that they are relevant to the\n construction of optimal codes. We attempt to make\n this note self contained, and describe the relevant\n results and proofs from the theory of\n pseudorandomness in some detail. }\n}\n\n","author_short":["Cheraghchi, M.","Shokrollahi, A.","Wigderson, A."],"key":"ref:conf:CSW06","id":"ref:conf:CSW06","bibbaseid":"cheraghchi-shokrollahi-wigderson-computationalhardnessandexplicitconstructionsoferrorcorrectingcodes-2006","role":"author","urls":{" paper":"https://infoscience.epfl.ch/record/101078"},"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T16:57:42.905Z","downloads":5,"keywords":[],"search_terms":["computational","hardness","explicit","constructions","error","correcting","codes","cheraghchi","shokrollahi","wigderson"],"title":"Computational Hardness and Explicit Constructions of Error Correcting Codes","year":2006,"dataSources":["YZqdBBx6FeYmvQE6D"]}