On approximate majority and probabilistic time

DOI10.1007/S00037-009-0267-3zbMath1217.68101OpenAlexW2173078028MaRDI QIDQ626665

Emanuele Viola

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-009-0267-3

zbMATH Keywords

lower boundtime-space tradeoffpseudorandom generatorpolynomial-time hierarchyapproximate majorityblack-boxalternating timeconstant-depth circuitprobabilistic timequasilinear time

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (14)

Expander-based cryptography meets natural proofs ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Skew Circuits of Small Width ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Skew circuits of small width ⋮ Randomness buys depth for approximate counting ⋮ Advice Coins for Classical and Quantum Computation ⋮ Unnamed Item ⋮ A robust version of Hegedűs's lemma, with applications ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ Unnamed Item

This page was built for publication: On approximate majority and probabilistic time