Randomness buys depth for approximate counting

DOI10.1007/s00037-013-0076-6zbMath1318.68091OpenAlexW2046927500MaRDI 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

randomnesssmall-depth circuitsapproximate majoritycombinatorial rectangle pseudorandom generator

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

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