Randomness buys depth for approximate counting

DOI10.1007/s00037-013-0076-6zbMath1318.68091MaRDI QIDQ483707

Emanuele Viola

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

zbMATH Keywords

randomness; small-depth circuits; approximate majority; combinatorial rectangle pseudorandom generator

Mathematics Subject Classification ID

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