The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899): Difference between revisions

@@ Property / author @@
-Eric W. Allender
@@ Property / author: Eric W. Allender / rank @@
-Normal rank
@@ Property / author @@
+Eric W. Allender
@@ Property / author: Eric W. Allender / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jcss.2010.06.004
+Normal rank
@@ Property / OpenAlex ID @@
+W2028930979
@@ Property / OpenAlex ID: W2028930979 / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of the existnce of pseudorandom generators
+Normal rank
@@ Property / cites work @@
+Q4474202
@@ Property / cites work: Q4474202 / rank @@
+Normal rank
@@ Property / cites work @@
+Avoiding Simplicity Is Complex
@@ Property / cites work: Avoiding Simplicity Is Complex / rank @@
+Normal rank
@@ Property / cites work @@
+Power from Random Strings
@@ Property / cites work: Power from Random Strings / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
+Normal rank
@@ Property / cites work @@
+A new general derandomization method
@@ Property / cites work: A new general derandomization method / rank @@
+Normal rank
@@ Property / cites work @@
+New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
+Normal rank
@@ Property / cites work @@
+ON HELPING AND INTERACTIVE PROOF SYSTEMS
@@ Property / cites work: ON HELPING AND INTERACTIVE PROOF SYSTEMS / rank @@
+Normal rank
@@ Property / cites work @@
+Non-deterministic exponential time has two-prover interactive protocols
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+Self-reducibility
@@ Property / cites work: Self-reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring
+Normal rank
@@ Property / cites work @@
+Derandomizing Arthur-Merlin games using hitting sets
+Normal rank
@@ Property / cites work @@
+Resource-Bounded Kolmogorov Complexity Revisited
@@ Property / cites work: Resource-Bounded Kolmogorov Complexity Revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Q4256650
@@ Property / cites work: Q4256650 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativized alternation and space-bounded computation
+Normal rank
@@ Property / cites work @@
+PSPACE is provable by two provers in one round
@@ Property / cites work: PSPACE is provable by two provers in one round / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness of approximate two-level logic minimization and PAC learning with membership queries
+Normal rank
@@ Property / cites work @@
+On resource-bounded instance complexity
@@ Property / cites work: On resource-bounded instance complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Storing a Sparse Table with             <i>0</i>             (1) Worst Case Access Time
+Normal rank
@@ Property / cites work @@
+An application of the translational method
@@ Property / cites work: An application of the translational method / rank @@
+Normal rank
@@ Property / cites work @@
+Data structures for distributed counting
@@ Property / cites work: Data structures for distributed counting / rank @@
+Normal rank
@@ Property / cites work @@
+Q3729902
@@ Property / cites work: Q3729902 / rank @@
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+A Pseudorandom Generator from any One-way Function
+Normal rank
@@ Property / cites work @@
+The strong exponential hierarchy collapses
@@ Property / cites work: The strong exponential hierarchy collapses / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Tape Simulation of Multitape Turing Machines
@@ Property / cites work: Two-Tape Simulation of Multitape Turing Machines / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform constant-depth threshold circuits for division and iterated multiplication.
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness vs time: Derandomization under a uniform assumption
+Normal rank
@@ Property / cites work @@
+Circuit minimization problem
@@ Property / cites work: Circuit minimization problem / rank @@
+Normal rank
@@ Property / cites work @@
+Circuit-size lower bounds and non-reducibility to sparse sets
+Normal rank
@@ Property / cites work @@
+Q4142699
@@ Property / cites work: Q4142699 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+On the Complexity of Learning Minimum Time-Bounded Turing Machines
+Normal rank
@@ Property / cites work @@
+Relativization of questions about log space computability
+Normal rank
@@ Property / cites work @@
+Randomness conservation inequalities; information and independence in mathematical theories
+Normal rank
@@ Property / cites work @@
+Symmetric space-bounded computation
@@ Property / cites work: Symmetric space-bounded computation / rank @@
+Normal rank
@@ Property / cites work @@
+An introduction to Kolmogorov complexity and its applications
+Normal rank
@@ Property / cites work @@
+Strong nondeterministic polynomial-time reducibilities
+Normal rank
@@ Property / cites work @@
+Algebraic methods for interactive proof systems
@@ Property / cites work: Algebraic methods for interactive proof systems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3263911
@@ Property / cites work: Q3263911 / rank @@
+Normal rank
@@ Property / cites work @@
+On uniformity within \(NC^ 1\)
@@ Property / cites work: On uniformity within \(NC^ 1\) / rank @@
+Normal rank
@@ Property / cites work @@
+Separating classes in the exponential-time hierarchy from classes in PH
+Normal rank
@@ Property / cites work @@
+Number-theoretic constructions of efficient pseudo-random functions
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+Upward separation for FewP and related classes
@@ Property / cites work: Upward separation for FewP and related classes / rank @@
+Normal rank
@@ Property / cites work @@
+Natural proofs
@@ Property / cites work: Natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Undirected connectivity in log-space
@@ Property / cites work: Undirected connectivity in log-space / rank @@
+Normal rank
@@ Property / cites work @@
+On uniform circuit complexity
@@ Property / cites work: On uniform circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic complexity classes and lowness
@@ Property / cites work: Probabilistic complexity classes and lowness / rank @@
+Normal rank
@@ Property / cites work @@
+Simple extractors for all min-entropies and a new pseudorandom generator
+Normal rank
@@ Property / cites work @@
+Pseudorandomness for approximate counting and sampling
+Normal rank
@@ Property / cites work @@
+Low-End Uniform Hardness versus Randomness Tradeoffs for AM
+Normal rank
@@ Property / cites work @@
+IP = PSPACE
@@ Property / cites work: IP = PSPACE / rank @@
+Normal rank
@@ Property / cites work @@
+A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
+Normal rank
@@ Property / cites work @@
+A natural encoding scheme proved probabilistic polynomial complete
+Normal rank
@@ Property / cites work @@
+AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
+Normal rank