Average-case intractability vs. worst-case intractability (Q598182): Difference between revisions

@@ Property / DOI @@
-.1016/j.ic.2003.05.002
@@ Property / DOI: 10.1016/j.ic.2003.05.002 / rank @@
-Normal rank
@@ Property / OpenAlex ID @@
+W2000641137
@@ Property / OpenAlex ID: W2000641137 / rank @@
+Normal rank
@@ Property / cites work @@
+On hiding information from an oracle
@@ Property / cites work: On hiding information from an oracle / rank @@
+Normal rank
@@ Property / cites work @@
+Q4281491
@@ Property / cites work: Q4281491 / rank @@
+Normal rank
@@ Property / cites work @@
+On pseudorandomness and resource-bounded measure
@@ Property / cites work: On pseudorandomness and resource-bounded measure / rank @@
+Normal rank
@@ Property / cites work @@
+New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
+Normal rank
@@ Property / cites work @@
+Upper bounds for the complexity of sparse and tally descriptions
+Normal rank
@@ Property / cites work @@
+Oracles and queries that are sufficient for exact learning
+Normal rank
@@ Property / cites work @@
+On the theory of average case complexity
@@ Property / cites work: On the theory of average case complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q4321931
@@ Property / cites work: Q4321931 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3359734
@@ Property / cites work: Q3359734 / 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 @@
+Q4418651
@@ Property / cites work: Q4418651 / rank @@
+Normal rank
@@ Property / cites work @@
+Quantitative Relativizations of Complexity Classes
+Normal rank
@@ Property / cites work @@
+Tally languages and complexity classes
@@ Property / cites work: Tally languages and complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Logarithmic advice classes
@@ Property / cites work: Logarithmic advice classes / rank @@
+Normal rank
@@ Property / cites work @@
+Robust reductions
@@ Property / cites work: Robust reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4251043
@@ Property / cites work: Q4251043 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4287358
@@ Property / cites work: Q4287358 / rank @@
+Normal rank
@@ Property / cites work @@
+Random-Self-Reducibility of Complete Sets
@@ Property / cites work: Random-Self-Reducibility of Complete Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q3999199
@@ Property / cites work: Q3999199 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounding the complexity of advice functions
@@ Property / cites work: Bounding the complexity of advice functions / rank @@
+Normal rank
@@ Property / cites work @@
+The power of the middle bit of a \(\#\)P function
@@ Property / cites work: The power of the middle bit of a \(\#\)P function / rank @@
+Normal rank
@@ Property / cites work @@
+Expected Computation Time for Hamiltonian Path problem
+Normal rank
@@ Property / cites work @@
+Highly resilient correctors for polynomials
@@ Property / cites work: Highly resilient correctors for polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Average case completeness
@@ Property / cites work: Average case completeness / rank @@
+Normal rank
@@ Property / cites work @@
+Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
+Normal rank
@@ Property / cites work @@
+On sparse sets in NP-P
@@ Property / cites work: On sparse sets in NP-P / rank @@
+Normal rank
@@ Property / cites work @@
+Computation times of NP sets of different densities
+Normal rank
@@ Property / cites work @@
+Locating \(P\)/poly optimally in the extended low hierarchy
+Normal rank
@@ Property / cites work @@
+On the power of generalized Mod-classes
@@ Property / cites work: On the power of generalized Mod-classes / rank @@
+Normal rank
@@ Property / cites work @@
+New Collapse Consequences of NP Having Small Circuits
+Normal rank
@@ Property / cites work @@
+BPP and the polynomial hierarchy
@@ Property / cites work: BPP and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Average Case Complete Problems
@@ Property / cites work: Average Case Complete Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4068103
@@ Property / cites work: Q4068103 / rank @@
+Normal rank
@@ Property / cites work @@
+Instance complexity
@@ Property / cites work: Instance complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity and structure
@@ Property / cites work: Complexity and structure / rank @@
+Normal rank
@@ Property / cites work @@
+Some properties of sets tractable under every polynomial-time computable distribution
+Normal rank
@@ Property / cites work @@
+A taxonomy of complexity classes of functions
@@ Property / cites work: A taxonomy of complexity classes of functions / rank @@
+Normal rank
@@ Property / cites work @@
+Structural average case complexity
@@ Property / cites work: Structural average case complexity / rank @@
+Normal rank
@@ Property / cites work @@
+PP is as Hard as the Polynomial-Time Hierarchy
@@ Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234079
@@ Property / cites work: Q4234079 / rank @@
+Normal rank
@@ Property / cites work @@
+On the NP-isomorphism problem with respect to random instances
+Normal rank
@@ Property / cites work @@
+Backtrack: An O(1) expected time algorithm for the graph coloring problem
+Normal rank
@@ Property / DOI @@
+.1016/J.IC.2003.05.002
@@ Property / DOI: 10.1016/J.IC.2003.05.002 / rank @@
+Normal rank