scientific article; zbMATH DE number 1405686
From MaRDI portal
Publication:4938667
zbMath0944.68074MaRDI QIDQ4938667
Osamu Watanabe, Peter Bro Miltersen, N. V. Vinodchandran
Publication date: 23 February 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (12)
Nonuniform ACC Circuit Lower Bounds ⋮ The size of SPP ⋮ On derandomization and average-case complexity of monotone functions ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Pseudo-deterministic Proofs ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Natural Proofs versus Derandomization ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Unnamed Item ⋮ AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly ⋮ Well spaced integers generated by an infinite set of primes
This page was built for publication:
