Randomness buys depth for approximate counting
From MaRDI portal
Publication:483707
DOI10.1007/s00037-013-0076-6zbMath1318.68091OpenAlexW2046927500MaRDI QIDQ483707
Publication date: 17 December 2014
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-013-0076-6
Related Items (6)
Paradigms for Unconditional Pseudorandom Generators ⋮ Bounded Independence Plus Noise Fools Products ⋮ Pseudo-Derandomizing Learning and Approximation ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On approximate majority and probabilistic time
- BPP and the polynomial hierarchy
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Linear-size constant-depth polylog-threshold circuits
- Pseudorandom generators for space-bounded computation
- The complexity of constructing pseudorandom generators from hard functions
- Derandomized graph products
- Improved pseudorandom generators for combinatorial rectangles
- Randomness is linear in space
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Pseudorandomness for network algorithms
- BQP and the polynomial hierarchy
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- On Approximation Algorithms for # P
- The complexity of promise problems with applications to public-key cryptography
- Eigenvalues and expansion of regular graphs
- Efficient approximation of product distributions
- Hardness Amplification Proofs Require Majority
This page was built for publication: Randomness buys depth for approximate counting
