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