scientific article; zbMATH DE number 2019635
From MaRDI portal
Publication:4440438
Recommendations
- Hardness and hierarchy theorems for probabilistic quasi-polynomial time
- More on BPP and the polynomial-time hierarchy
- New non-uniform lower bounds for uniform classes
- Heuristic time hierarchies via hierarchies for sampling distributions
- Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
Cited in
(21)- New non-uniform lower bounds for uniform classes
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax
- Non-interactive universal arguments
- Worst-Case to Average-Case Reductions for Subclasses of P
- Randomness and intractability in Kolmogorov complexity
- Time hierarchies for cryptographic function inversion with advice
- Hardness and hierarchy theorems for probabilistic quasi-polynomial time
- Computation with finite stochastic chemical reaction networks
- From logarithmic advice to single-bit advice
- The power of natural properties as oracles
- A linear-time algorithm for computing the multinomial stochastic complexity
- scientific article; zbMATH DE number 4205978 (Why is no real title available?)
- Heuristic time hierarchies via hierarchies for sampling distributions
- Structural complexity of AvgBPP
- On approximate majority and probabilistic time
- Pseudodeterministic algorithms and the structure of probabilistic time
- Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
- Almost-everywhere complexity hierarchies for nondeterministic time
- Structural Complexity of AvgBPP
- Circuit lower bounds for average-case MA
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 Q4440438)
