Article

Free access

On the efficiency of local decoding procedures for error-correcting codes

Authors:

Jonathan Katz,

Luca TrevisanAuthors Info & Claims

STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing

Pages 80 - 86

https://doi.org/10.1145/335305.335315

Published: 01 May 2000 Publication History

PDF eReader

References

[1]

A. Ambainis. Upper bounds on the communication complexity of private information retrieval. In Proceedings of ICALP, pages 401-407, 1997.

Digital Library

Google Scholar

[2]

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. Journal of the A CM, 45(3):501-555, 1998. Preliminary version in Proc. of FOCS'92.

Digital Library

Google Scholar

[3]

S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the A CM, 45(1):70-122, 1998. Preliminary version in Proc. of FOC$'92.

Digital Library

Google Scholar

[4]

L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd A CM Symposium on Theory of Computing, pages 21-31, 1991.

Digital Library

Google Scholar

[5]

L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXP- TIME has publishable proofs. Computational Complexity, 3(4):307-318, 1993.

Digital Library

Google Scholar

[6]

D. Beaver and J. Feigenbaum. Hiding instances in multi-oracle queries. In 7th Annual Symposium on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, pages 37-48, Rouen, France, 22-24 February 1990. Springer.

Digital Library

Google Scholar

[7]

B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. Journal of the A CM, 45(6), 1998. Preliminary version in Proc. of FOCS'95.

Digital Library

Google Scholar

[8]

J. Feigenbaum and L. Fortnow. Random selfreducibility of complete sets. SIAM Journal on Computing, 22(5):994-1005, October 1993.

Digital Library

Google Scholar

[9]

P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proceedings of the Twenty Th4rd Annual A CM Symposium on Theory of Computing, pages 32-42, New Orleans, Louisiana, 6-8 May 1991.

Digital Library

Google Scholar

[10]

P. Gemmell and M. Sudan. Highly resilient correctots for polynomials. Information Processing Letters, 43(4):169-174, 28 September 1992.

Digital Library

Google Scholar

[11]

O. Goldreich. Personal communication. September 1999.

Google Scholar

[12]

L. Levin. Research overview. http://ww~, cs. bu. edu/f ac/lnd/res earch/res, html.

Google Scholar

[13]

R. Lipton. New directions in testing. In Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, 1989.

Google Scholar

[14]

E. Mann. Private access to distributed information. Master's Thesis, Technion, 1998.

Google Scholar

[15]

A. Polishchuk and D.A. Spielman. Nearly linear-size holographic proofs. In Proceedings of the ~6th A CM Symposium on Theory of Computing, pages 194-203, 1994.

Digital Library

Google Scholar

[16]

M. Sudan, L. Trevisan, and S. Vadhan. Pseudorandom generators without the XOR lemma. In Proceedings of the 31st A CM Symposium on Theory of Computing, pages 537-546, 1999.

Digital Library

Google Scholar

Cited By

View all

Arunachalam SDoriguello J(2024)Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet caseACM Transactions on Computation Theory10.1145/368882416:4(1-38)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3688824
Gupta MMohar BShinkar IO'Donnell R(2024)Constant Query Local Decoding against Deletions Is ImpossibleProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649655(752-763)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649655
Kothari PManohar PMohar BShinkar IO'Donnell R(2024)An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649640(776-787)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649640
Show More Cited By

Index Terms

On the efficiency of local decoding procedures for error-correcting codes

Recommendations

Decoding error-correcting codes via linear programming
Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams

Coding in the projective space has received recently a lot of attention due to its application in network coding. Reduced row echelon form of the linear subspaces and Ferrers diagram can playa key role for solving coding problems in the projective ...
Optimal Unidirectional Error Detecting/Correcting Codes

In this correspondence a class of t-error correcting and multiple unidirectional error detecting systematic codes is presented. These codes are significantly more efficient than the earlier codes. The efficiency of these codes approaches the efficiency ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing

May 2000

756 pages

ISBN:1581131844

DOI:10.1145/335305

Chairmen:
Frances Yao,
Eugene Luks

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC00

Sponsor:

SIGACT

STOC00: The 32nd Annual ACM Symposium on Theory of Computing

May 21 - 23, 2000

Oregon, Portland, USA

Acceptance Rates

STOC '00 Paper Acceptance Rate 85 of 182 submissions, 47%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

230
Total Citations
View Citations
1,631
Total Downloads

Downloads (Last 12 months)296
Downloads (Last 6 weeks)37

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Arunachalam SDoriguello J(2024)Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet caseACM Transactions on Computation Theory10.1145/368882416:4(1-38)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3688824
Gupta MMohar BShinkar IO'Donnell R(2024)Constant Query Local Decoding against Deletions Is ImpossibleProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649655(752-763)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649655
Kothari PManohar PMohar BShinkar IO'Donnell R(2024)An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649640(776-787)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649640
Kumar VMon GMohar BShinkar IO'Donnell R(2024)Relaxed Local Correctability from Local TestingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649611(1585-1593)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649611
Li ZSun H(2024)On Extremal Rates of Storage Over GraphsIEEE Transactions on Information Theory10.1109/TIT.2023.332843470:4(2464-2478)Online publication date: Apr-2024
https://doi.org/10.1109/TIT.2023.3328434
Mon GMoshkovitz DOh J(2024)Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619326(2838-2843)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619326
Block ABlocki JCheng KGrigorescu ELi XZheng YZhu M(2023)On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion ErrorsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.14(1-25)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.14
Newton PRichelson SWilson CSaha BServedio R(2023)A High Dimensional Goldreich-Levin TheoremProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585224(1463-1474)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585224
Alrabiah OGuruswami VKothari PManohar PSaha BServedio R(2023)A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP RefutationProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585143(1438-1448)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585143
Block ABlocki J(2023)Computationally Relaxed Locally Decodable Codes, Revisited2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206655(2714-2719)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206655
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Decoding error-correcting codes via linear programming

Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams

Optimal Unidirectional Error Detecting/Correcting Codes