Pages that link to "Item:Q1190984"
From MaRDI portal
The following pages link to On the theory of average case complexity (Q1190984):
Displaying 50 items.
- Is Valiant-Vazirani's isolation probability improvable? (Q354652) (← links)
- An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems (Q464980) (← links)
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- All natural NP-complete problems have average-case complete versions (Q626691) (← links)
- Structural complexity of AvgBPP (Q638488) (← links)
- Complete problems with L-samplable distributions (Q804284) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- On the IO-complexity and approximation languages (Q1112018) (← links)
- A note on the best-case complexity (Q1120281) (← links)
- Average case complexity under the universal distribution equals worst- case complexity (Q1198047) (← links)
- Learning with restricted focus of attention (Q1271613) (← links)
- Reductions do not preserve fast convergence rates in average time (Q1283684) (← links)
- Some properties of sets tractable under every polynomial-time computable distribution (Q1350351) (← links)
- An average complexity measure that yields tight hierarchies (Q1355380) (← links)
- Batch Diffie-Hellman key agreement systems (Q1363070) (← links)
- No NP problems averaging over ranking of distributions are harder (Q1391309) (← links)
- Complete distributional problems, hard languages, and resource-bounded measure (Q1575682) (← links)
- Polynomial time samplable distributions (Q1578504) (← links)
- Encoding invariance in average case complexity (Q1678756) (← links)
- The difference between polynomial-time many-one and truth-table reducibilities on distributional problems (Q1849751) (← links)
- Malign distributions for average case circuit complexity. (Q1854270) (← links)
- Complete on average Boolean satisfiability (Q1872642) (← links)
- Structural average case complexity (Q1916530) (← links)
- The computational complexity of generating random fractals (Q1946896) (← links)
- Computational depth: Concept and applications (Q2368976) (← links)
- Secret sharing based on a hard-on-average problem (Q2369061) (← links)
- The query complexity of witness finding (Q2411034) (← links)
- Notes on Levin’s Theory of Average-Case Complexity (Q3088187) (← links)
- Average Case Complexity, Revisited (Q3088195) (← links)
- Structural Complexity of AvgBPP (Q3392950) (← links)
- (Q3413362) (← links)
- Average-Case Complexity (Q3522267) (← links)
- An infinitely-often one-way function based on an average-case assumption (Q3586759) (← links)
- On Average Case Complexity of SAT for Symmetric Distribution (Q4323003) (← links)
- (Q4336271) (← links)
- (Q4399282) (← links)
- Malign distributions for average case circuit complexity (Q4596659) (← links)
- The Journey from NP to TFNP Hardness (Q4638115) (← links)
- The complexity of generating test instances (Q5048939) (← links)
- Complete problems with L-samplable distributions (Q5056117) (← links)
- (Q5072483) (← links)
- Average-Case Completeness in Tag Systems (Q5090467) (← links)
- On the average complexity of the $k$-level (Q5132651) (← links)
- (Q5140842) (← links)
- Derandomizing Isolation in Space-Bounded Settings (Q5232318) (← links)
- Fundamentals of Computation Theory (Q5900806) (← links)
- Distributionally hard languages (Q5945724) (← links)
- Sets computable in polynomial time on average (Q6085734) (← links)
- Rankable distributions do not provide harder instances than uniform distributions (Q6085735) (← links)
- Structure in average case complexity (Q6487946) (← links)
