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.
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?)
- scientific article; zbMATH DE number 1104164 (Why is no real title available?)
- scientific article; zbMATH DE number 2011836 (Why is no real title available?)
- scientific article; zbMATH DE number 1759459 (Why is no real title available?)
- 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)
