An efficient coding theorem via probabilistic representations and its applications

DOI10.4230/LIPICS.ICALP.2021.94MaRDI QIDQ7241194zbMATH OpenFDO

Authors Zhenjian Lu, Igor C. Oliveira

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.94

zbMATH Keywords

computational complexityKolmogorov complexityrandomized algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A Chernoff Bound for Random Walks on Expander Graphs
• An introduction to Kolmogorov complexity and its applications
• Compression and Ranking
• Compression of samplable sources
• Deterministic methods to find primes
• Elements of Information Theory
• Explicit constructions of linear-sized superconcentrators
• Hardness magnification for all sparse NP languages
• Hardness magnification near state-of-the-art lower bounds
• scientific article; zbMATH DE number 107775 (Why is no real title available?)
• scientific article; zbMATH DE number 3489017 (Why is no real title available?)
• scientific article; zbMATH DE number 2081089 (Why is no real title available?)
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• scientific article; zbMATH DE number 2196513 (Why is no real title available?)
• Introduction to analytic and probabilistic number theory. Transl. from the 3rd French edition by Patrick D. F. Ion
• Kolmogorov Complexity and Algorithmic Randomness
• Language compression and pseudorandom generators
• Learning algorithms from natural proofs
• Linear-time encodable and decodable error-correcting codes
• Natural proofs
• Non-black-box worst-case to average-case reductions within NP
• On symmetry of information and polynomial time invertibility
• Power from Random Strings
• Pseudodeterministic constructions in subexponential time
• Randomness and intractability in Kolmogorov complexity
• Randomness conservation inequalities; information and independence in mathematical theories
• Sharp threshold results for computational complexity
• Short lists with short programs in short time
• Symmetry of information and one-way functions
• The Complexity of Complexity
• The twin prime conjecture
• Time hierarchies for sampling distributions

This page was built for publication: An efficient coding theorem via probabilistic representations and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241194)