Large sets in AC^0 have many strings with low Kolmogorov complexity

DOI10.1016/S0020-0190(97)00054-9zbMATH Open1337.68142OpenAlexW2046926619MaRDI QIDQ290244FDOQ290244

Authors Marius Zimand 

Publication date 1 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00054-9

zbMATH Keywords

Kolmogorov complexity\(\mathrm{AC}^{0}\)

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Avoiding simplicity is complex
• Avoiding simplicity is complex
• Power from Random Strings
• scientific article; zbMATH DE number 3974293
• Sets with small generalized Kolmogorov complexity

Cites Work

• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• Pseudorandom bits for constant depth circuits
• Pseudorandom generators and the frequency of simplicity
• Some consequences of the existnce of pseudorandom generators
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

Cited In (1)

• A comparison of two approaches to pseudorandomness

This page was built for publication: Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity

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