scientific article; zbMATH DE number 2081089

MaRDI QIDQ4474202zbMATH OpenFDO

Authors Eric Allender

Publication date 4 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2245/22450001.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 7701424
• Randomness and intractability in Kolmogorov complexity
• Logical Approaches to Computational Barriers
• Limits on the Computational Power of Random Strings
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory

Cited in

(20)

• Nonuniform reductions and NP-completeness
• NL-printable sets and nondeterministic Kolmogorov complexity
• Dimension, entropy rates, and compression
• A note on dimensions of polynomial size circuits
• NL-printable sets and nondeterministic Kolmogorov complexity
• Randomness and intractability in Kolmogorov complexity
• Hardness magnification near state-of-the-art lower bounds
• Logical Approaches to Computational Barriers
• A circuit complexity formulation of algorithmic information theory
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Constructive separations and their consequences
• A direct PRF construction from Kolmogorov complexity
• Avoiding simplicity is complex
• NP-hardness of approximating meta-complexity: a cryptographic approach
• One-way functions and pKt complexity
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
• Lower bounds for Levin-Kolmogorov complexity
• On the structure of learnability beyond \textsf{P/poly}
• An efficient coding theorem via probabilistic representations and its applications

This page was built for publication:

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