Randomness buys depth for approximate counting
From MaRDI portal
Publication:483707
DOI10.1007/s00037-013-0076-6zbMath1318.68091MaRDI 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
randomness; small-depth circuits; approximate majority; combinatorial rectangle pseudorandom generator
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Bounded Independence Plus Noise Fools Products, A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem], Unnamed Item, Pseudo-Derandomizing Learning and Approximation, Fourier bounds and pseudorandom generators for product tests, Paradigms for Unconditional Pseudorandom Generators
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