Some Applications of Coding Theory in Computational Complexity

zbMath1072.94018arXivcs/0409044MaRDI QIDQ5465364

Luca Trevisan

Publication date: 22 August 2005

Full work available at URL: https://arxiv.org/abs/cs/0409044

zbMATH Keywords

computational complexity; error correction; coding language

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94-02: Research exposition (monographs, survey articles) pertaining to information and communication theory

68-02: Research exposition (monographs, survey articles) pertaining to computer science

94B99: Theory of error-correcting codes and error-detecting codes

94B35: Decoding

Related Items

General constructions for information-theoretic private information retrieval