On approximate majority and probabilistic time

DOI10.1007/S00037-009-0267-3MaRDI QIDQ626665zbMATH OpenOpenAlexFDO

Authors 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 boundapproximate majorityblack-boxpolynomial-time hierarchypseudorandom generatoralternating timeconstant-depth circuitprobabilistic timequasilinear timetime-space tradeoff

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6851888
• On randomized complexity of functions approximating the majority function
• On randomized algorithms for the majority problem
• Time-space trade-offs in population protocols for the majority problem
• Pseudodeterministic algorithms and the structure of probabilistic time
• The Average-Case Complexity of Determining the Majority
• Randomized algorithms for the majority problem
• scientific article; zbMATH DE number 2019635
• Tight bounds on expected time to add correctly and add mostly correctly
• Deterministic approximation of the cover time

Cited in

(21)

• Fourier bounds and pseudorandom generators for product tests
• A robust version of Hegedűs's lemma, with applications
• Expander-based cryptography meets natural proofs
• Hardness and hierarchy theorems for probabilistic quasi-polynomial time
• Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
• Pseudorandom bits and lower bounds for randomized Turing machines
• Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Size bounds on low depth circuits for promise majority
• scientific article; zbMATH DE number 6851888 (Why is no real title available?)
• Quantified Derandomization: How to Find Water in the Ocean
• Skew circuits of small width
• Pseudorandomness, symmetry, smoothing: I
• Randomness buys depth for approximate counting
• Skew circuits of small width
• Advice coins for classical and quantum computation
• Tight bounds on expected time to add correctly and add mostly correctly
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Towards simpler sorting networks and monotone circuits for majority
• Bounded indistinguishability and the complexity of recovering secrets
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626665)