The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
From MaRDI portal
Publication:619899
Recommendations
Cites work
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- A natural encoding scheme proved probabilistic polynomial complete
- A new general derandomization method
- A Pseudorandom Generator from any One-way Function
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Algebraic methods for interactive proof systems
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- An application of the translational method
- An introduction to Kolmogorov complexity and its applications
- Avoiding simplicity is complex
- Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring
- Circuit minimization problem
- Circuit-size lower bounds and non-reducibility to sparse sets
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Data structures for distributed counting
- Derandomizing Arthur-Merlin games using hitting sets
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
- Hardness vs randomness
- scientific article; zbMATH DE number 3145789 (Why is no real title available?)
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 1318518 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 2081089 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- IP = PSPACE
- Low-End Uniform Hardness versus Randomness Tradeoffs for AM
- Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
- Natural proofs
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Non-deterministic exponential time has two-prover interactive protocols
- Number-theoretic constructions of efficient pseudo-random functions
- ON HELPING AND INTERACTIVE PROOF SYSTEMS
- On resource-bounded instance complexity
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- On uniform circuit complexity
- On uniformity within \(NC^ 1\)
- Power from Random Strings
- Probabilistic complexity classes and lowness
- Pseudorandomness for approximate counting and sampling
- PSPACE is provable by two provers in one round
- Randomness conservation inequalities; information and independence in mathematical theories
- Randomness vs time: Derandomization under a uniform assumption
- Relativization of questions about log space computability
- Relativized alternation and space-bounded computation
- Resource-bounded Kolmogorov complexity revisited
- Self-reducibility
- Separating classes in the exponential-time hierarchy from classes in PH
- Simple extractors for all min-entropies and a new pseudorandom generator
- Some consequences of the existnce of pseudorandom generators
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Strong nondeterministic polynomial-time reducibilities
- Symmetric space-bounded computation
- The complexity of theorem-proving procedures
- The strong exponential hierarchy collapses
- Two-Tape Simulation of Multitape Turing Machines
- Undirected connectivity in log-space
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Upward separation for FewP and related classes
Cited in
(36)- Algorithmic networks: central time to trigger expected emergent open-endedness
- The minimum oracle circuit size problem
- Resource-bounded Kolmogorov complexity revisited
- Asymptotic density and the coarse computability bound
- The Complexity of Complexity
- On Resource-Bounded Versions of the van Lambalgen Theorem
- Limits on the Computational Power of Random Strings
- Minimum circuit size, graph isomorphism, and related problems
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- Generation Complexity Versus Distinction Complexity
- Avoiding simplicity is complex
- scientific article; zbMATH DE number 3988704 (Why is no real title available?)
- scientific article; zbMATH DE number 107775 (Why is no real title available?)
- scientific article; zbMATH DE number 1335892 (Why is no real title available?)
- scientific article; zbMATH DE number 2081089 (Why is no real title available?)
- Minimum circuit size, graph isomorphism, and related problems
- Resource-bounded Kolmogorov complexity revisited
- Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
- Randomness and intractability in Kolmogorov complexity
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- scientific article; zbMATH DE number 7561759 (Why is no real title available?)
- scientific article; zbMATH DE number 7204388 (Why is no real title available?)
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- On parametric timed automata and one-counter machines
- The non-hardness of approximating circuit size
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- scientific article; zbMATH DE number 7701424 (Why is no real title available?)
- The complexity of Boolean formula minimization
- One-tape Turing machine and branching program lower bounds for MCSP
- Constant depth formula and partial function versions of MCSP are hard
- Gap MCSP is not (Levin) NP-complete in obfustopia
- Avoiding simplicity is complex
- Lower bounds for Levin-Kolmogorov complexity
- Brief announcement: Optimally encoding information in chemical reaction networks
- One-tape Turing machine and branching program lower bounds for MCSP
This page was built for publication: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619899)
