On approximate majority and probabilistic time
From MaRDI portal
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
(17)- 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\)
- 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
- 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
- Bounded indistinguishability and the complexity of recovering secrets
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)
