Some Applications of Coding Theory in Computational Complexity
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Decoding (94B35) Theory of error-correcting codes and error-detecting codes (94B99)
Abstract: Error-correcting codes and related combinatorial constructs play an important role in several recent (and old) results in computational complexity theory. In this paper we survey results on locally-testable and locally-decodable error-correcting codes, and their applications to complexity theory and to cryptography. Locally decodable codes are error-correcting codes with sub-linear time error-correcting algorithms. They are related to private information retrieval (a type of cryptographic protocol), and they are used in average-case complexity and to construct ``hard-core predicates for one-way permutations. Locally testable codes are error-correcting codes with sub-linear time error-detection algorithms, and they are the combinatorial core of probabilistically checkable proofs.
The author studies in detail an application of coding theory in computational complexity and explains error correcting, sublinear time decoding, list decoding and locally testable codes. It is quite interesting that the author gives a full list of references for any one who is interested to redo the study in his own perspective. It is an interesting article to read. For the entire collection see [Zbl 1062.68004].
Recommendations
- scientific article; zbMATH DE number 837790
- scientific article; zbMATH DE number 1104300
- scientific article; zbMATH DE number 1284420
- scientific article; zbMATH DE number 606784
- scientific article; zbMATH DE number 3409222
- Applications of coding theory to communication combinatorial problems
- Coding Theory Applied to a Problem of Ulam
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- scientific article; zbMATH DE number 3616338
- On some topics in combinatorial coding theory
Cited in
(36)- Coding theory. Abstracts from the workshop held December 2--8, 2007.
- Query-efficient locally decodable codes of subexponential length
- On the complexity of decision problems for counter machines with applications to coding theory
- Simple extractors via constructions of cryptographic pseudo-random generators
- General constructions for information-theoretic private information retrieval
- A quadratic lower bound for three-query linear locally decodable codes over any field
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Public key locally decodable codes with short keys
- scientific article; zbMATH DE number 1004583 (Why is no real title available?)
- scientific article; zbMATH DE number 4083538 (Why is no real title available?)
- An Application of Set Theory to Coding Theory
- scientific article; zbMATH DE number 1335886 (Why is no real title available?)
- Algorithmic issues in coding theory
- Error-correcting codes in complexity theory
- List decoding: Algorithms and applications
- Links between complexity theory and constrained block coding
- scientific article; zbMATH DE number 837790 (Why is no real title available?)
- Limitation on the Rate of Families of Locally Testable Codes
- Composition of semi-LTCs by two-wise tensor products
- On the power of relaxed local decoding algorithms
- scientific article; zbMATH DE number 7310074 (Why is no real title available?)
- Some Problems in Organic Coding Theory
- A simple derivation of the coding theorem and some applications
- A survey of progress in coding theory in the Soviet Union
- scientific article; zbMATH DE number 3409222 (Why is no real title available?)
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR
- Erasures versus errors in local decoding and property testing
- On matrix rigidity and locally self-correctable codes
- On Linear Complexity of Finite Sequences: Coding Theory and Applications to Cryptography
- (Quantum) complexity of testing signed graph clusterability
- Noisy decoding by shallow circuits with parities: classical and quantum (extended abstract)
- Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Contemporary coding theory. Abstracts from the workshop held March 17--23, 2019
- Applications of coding theory to communication combinatorial problems
This page was built for publication: Some Applications of Coding Theory in Computational Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5465364)
