Computational depth: Concept and applications

DOI10.1016/J.TCS.2005.11.033MaRDI QIDQ2368976zbMATH OpenOpenAlexFDO

Authors Dieter Van Melkebeek, N. V. Vinodchandran, Luís Antunes, Lance Fortnow

Publication date 28 April 2006

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

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

zbMATH Keywords

Kolmogorov complexityStructural complexity and average case complexity

Mathematics Subject Classification ID

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

Recommendations

• Low-depth witnesses are easy to find
• Computational depth and reducibility
• Using depth to capture average-case complexity.
• Depth as randomness deficiency
• On the Polynomial Depth of Various Sets of Random Strings

Cites work

• Average Case Complete Problems
• Average case complexity under the universal distribution equals worst- case complexity
• Hardness vs randomness
• scientific article; zbMATH DE number 3990861 (Why is no real title available?)
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 1256744 (Why is no real title available?)
• scientific article; zbMATH DE number 1304330 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1072538 (Why is no real title available?)
• scientific article; zbMATH DE number 1136072 (Why is no real title available?)
• On resource-bounded instance complexity
• On the theory of average case complexity
• Randomness conservation inequalities; information and independence in mathematical theories
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Resource-bounded Kolmogorov complexity revisited
• The Complexity of Malign Measures
• Using depth to capture average-case complexity.

Cited in

(34)

• Computational depth and reducibility
• High-dimensional computation of the deepest location.
• Lowness and logical depth
• On the polynomial depth of various sets of random strings
• Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)
• Searching for shortest and least programs
• Computation of depth in \(C(X)\)
• Polylog depth, highness and lowness for E
• Relativized depth
• Algorithmic statistics revisited
• Two Problems for Sophistication
• Depth, highness and DNR degrees
• Algorithmic statistics: forty years later
• On the Polynomial Depth of Various Sets of Random Strings
• The fundamental difference between depth and delay
• On the difference between finite-state and pushdown depth
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• Low-depth witnesses are easy to find
• Sophistication vs logical depth
• Computing Depths of Patterns
• Feasible Depth
• Using depth to capture average-case complexity.
• Pushdown and Lempel-Ziv depth
• Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics)
• Capturing one-way functions via NP-hardness of meta-complexity
• Pebble-depth
• Search-to-decision reductions for Kolmogorov complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
• A meta-complexity theoretic approach to indistinguishability obfuscation and witness pseudo-canonicalization
• Depth as randomness deficiency
• Sophistication revisited
• Information measures for infinite sequences
• Time-bounded incompressibility of compressible strings and sequences

This page was built for publication: Computational depth: Concept and applications

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