Resource bounded symmetry of information revisited

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

Andrei Romashchenko, Troy Lee

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

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

zbMATH Keywords

Kolmogorov complexityCompressionSymmetry of information

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• Symmetry in information flow
• On symmetry and the directed divergence in information theory
• Compression of samplable sources
• Symmetry of information and one-way functions
• On optimal language compression for sets in PSPACE/poly
• Symmetry of Information: A Closer Look
• Symmetry of Information and Nonuniform Lower Bounds
• On symmetry of information and polynomial time invertibility
• A duality between one-way functions and average-case symmetry of information
• Title not available (Why is that?)
• Some properties of antistochastic strings
• On the Optimal Compression of Sets in PSPACE
• Mathematical Foundations of Computer Science 2004
• On Resource-Bounded Versions of the van Lambalgen Theorem

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)