Avoiding simplicity is complex
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 2081089 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- A Pseudorandom Generator from any One-way Function
- Algebraic methods for interactive proof systems
- Avoiding simplicity is complex
- Computational Complexity
- IP = PSPACE
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Non-deterministic exponential time has two-prover interactive protocols
- Polynomial-time compression
- Power from Random Strings
- Randomness conservation inequalities; information and independence in mathematical theories
- Resource-bounded Kolmogorov complexity revisited
- Separating NE from Some Nonuniform Nondeterministic Complexity Classes
- Separating Nondeterministic Time Complexity Classes
- Some consequences of the existnce of pseudorandom generators
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Unconditional Lower Bounds against Advice
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
Cited in
(8)- scientific article; zbMATH DE number 5360956 (Why is no real title available?)
- Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
- Closure and nonclosure properties of the classes of compressible and rankable sets
- Simplicity Is the Point
- What Simplicity Is Not
- Avoiding simplicity is complex
- Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity
- Simplify or perish
This page was built for publication: Avoiding simplicity is complex
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693072)