scientific article; zbMATH DE number 1335875
From MaRDI portal
Publication:4258566
zbMath0935.68032MaRDI QIDQ4258566
Harry Buhrman, Thomas Thierauf, Lance J. Fortnow
Publication date: 13 September 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (21)
New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ In search of an easy witness: Exponential time vs. probabilistic polynomial time. ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Circuit Lower Bounds for Average-Case MA ⋮ Robust simulations and significant separations ⋮ The power of natural properties as oracles ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Sparse selfreducible sets and nonuniform lower bounds ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Unnamed Item ⋮ Two Variable vs. Linear Temporal Logic in Model Checking and Games ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly ⋮ Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly ⋮ Unifying known lower bounds via geometric complexity theory
This page was built for publication:
