Resource bounded symmetry of information revisited

DOI10.1016/J.TCS.2005.07.017zbMATH Open1081.68034OpenAlexW1971142267MaRDI QIDQ2575757FDOQ2575757

Authors Troy Lee, Andrei Romashchenko 

Publication date 6 December 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.07.017

zbMATH Keywords

Kolmogorov complexityCompressionSymmetry of information

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Mathematical Foundations of Computer Science 2004
• On symmetry of information and polynomial time invertibility
• scientific article; zbMATH DE number 1335898
• Symmetry of information and one-way functions
• Symmetry of Information and Nonuniform Lower Bounds

Cites work

• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 475434 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1775405 (Why is no real title available?)
• Compression of samplable sources
• Extracting all the randomness and reducing the error in Trevisan's extractors
• Extractors and pseudorandom generators
• Hardness vs randomness
• Mathematical Foundations of Computer Science 2004
• NP is as easy as detecting unique solutions
• On resource-bounded instance complexity
• On symmetry of information and polynomial time invertibility
• Resource-bounded Kolmogorov complexity revisited
• Some observations on the probabilistic algorithms and NP-hard problems
• Symmetry of information and one-way functions
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The complexity of agreement
• Two heads are better than two tapes

Cited in

(14)

• On optimal language compression for sets in PSPACE/poly
• Asymmetry of the Kolmogorov complexity of online predicting odd and even bits
• Symmetry in information flow
• A duality between one-way functions and average-case symmetry of information
• Mathematical Foundations of Computer Science 2004
• On the optimal compression of sets in PSPACE
• Symmetry of information and one-way functions
• Symmetry of Information: A Closer Look
• On symmetry of information and polynomial time invertibility
• On Resource-Bounded Versions of the van Lambalgen Theorem
• scientific article; zbMATH DE number 3871178 (Why is no real title available?)
• Symmetry of Information and Nonuniform Lower Bounds
• Compression of samplable sources
• On symmetry and the directed divergence in information theory

This page was built for publication: Resource bounded symmetry of information revisited

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