scientific article; zbMATH DE number 512870
From MaRDI portal
Publication:4281567
Recommendations
Cited in
(23)- On the theory of average case complexity
- Average case complexity under the universal distribution equals worst- case complexity
- Reductions do not preserve fast convergence rates in average time
- Some properties of sets tractable under every polynomial-time computable distribution
- An average complexity measure that yields tight hierarchies
- No NP problems averaging over ranking of distributions are harder
- Encoding invariance in average case complexity
- Structural average case complexity
- scientific article; zbMATH DE number 999544 (Why is no real title available?)
- scientific article; zbMATH DE number 5081744 (Why is no real title available?)
- Average-Case Complexity
- On the Average Case Complexity of Some P-complete Problems
- Instance complexity
- scientific article; zbMATH DE number 1008511 (Why is no real title available?)
- Complexity of distributions and average-case hardness
- Average-case fine-grained hardness
- Using depth to capture average-case complexity.
- Distributionally hard languages
- Rankable distributions do not provide harder instances than uniform distributions
- Average circuit depth and average communication complexity
- Reductions and convergence rates of average time
- All natural NP-complete problems have average-case complete versions
- Structure in average case complexity
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4281567)
