Some Applications of Coding Theory in Computational Complexity
From MaRDI portal
Publication:5465364
zbMath1072.94018arXivcs/0409044MaRDI QIDQ5465364
Publication date: 22 August 2005
Full work available at URL: https://arxiv.org/abs/cs/0409044
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Theory of error-correcting codes and error-detecting codes (94B99) Decoding (94B35)
Related Items (15)
A quadratic lower bound for three-query linear locally decodable codes over any field ⋮ On locally decodable codes, self-correctable codes, and \(t\)-private PIR ⋮ Erasures versus errors in local decoding and property testing ⋮ Query-efficient locally decodable codes of subexponential length ⋮ On matrix rigidity and locally self-correctable codes ⋮ Composition of semi-LTCs by two-wise tensor products ⋮ General constructions for information-theoretic private information retrieval ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Simple extractors via constructions of cryptographic pseudo-random generators ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Public Key Locally Decodable Codes with Short Keys ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Unnamed Item ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
This page was built for publication: Some Applications of Coding Theory in Computational Complexity
