scientific article; zbMATH DE number 2019635

zbMATH Open1028.68058MaRDI QIDQ4440438FDOQ4440438

Boaz Barak

Publication date: 17 December 2003

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2483/24830194.htm

Title of this publication is not available (Why is that?)

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

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (20)

• Title not available (Why is that?)
• 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
• Time hierarchies for cryptographic function inversion with advice
• Circuit Lower Bounds for Average-Case MA
• Computation with finite stochastic chemical reaction networks
• Title not available (Why is that?)
• The power of natural properties as oracles
• Robust simulations and significant separations
• A linear-time algorithm for computing the multinomial stochastic complexity
• Title not available (Why is that?)
• Natural proofs versus derandomization
• Structural complexity of AvgBPP
• Pseudodeterministic algorithms and the structure of probabilistic time
• From Logarithmic Advice to Single-Bit Advice
• On approximate majority and probabilistic time
• Randomness and Intractability in Kolmogorov Complexity
• Almost-everywhere complexity hierarchies for nondeterministic time
• Structural Complexity of AvgBPP

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)