Randomness buys depth for approximate counting

DOI10.1007/S00037-013-0076-6zbMATH Open1318.68091OpenAlexW2046927500MaRDI QIDQ483707FDOQ483707

Authors: 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

Recommendations

• Improved pseudorandom generators for depth 2 circuits
• scientific article; zbMATH DE number 1833418
• Hardness vs randomness
• Pseudorandom bits for constant depth circuits
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials

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)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On Approximation Algorithms for # P
• Derandomized graph products
• BPP and the polynomial hierarchy
• Pseudorandomness for network algorithms
• The complexity of promise problems with applications to public-key cryptography
• The complexity of constructing pseudorandom generators from hard functions
• Title not available (Why is that?)
• Hardness Amplification Proofs Require Majority
• Randomness is linear in space
• Eigenvalues and expansion of regular graphs
• BQP and the polynomial hierarchy
• Title not available (Why is that?)
• Pseudorandom generators for space-bounded computation
• Improved pseudorandom generators for combinatorial rectangles
• Efficient approximation of product distributions
• Title not available (Why is that?)
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Linear-size constant-depth polylog-threshold circuits
• A primer on pseudorandom generators
• Bounds on the Size of Small Depth Circuits for Approximating Majority
• Title not available (Why is that?)
• On approximate majority and probabilistic time

Cited In (10)

• A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
• Fourier bounds and pseudorandom generators for product tests
• Pseudo-derandomizing learning and approximation
• Paradigms for Unconditional Pseudorandom Generators
• The complexity of distributions
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Optimal explicit small-depth formulas for the coin problem
• Bounded independence plus noise fools products
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Randomness-efficient sampling within NC\(^{1}\)

This page was built for publication: Randomness buys depth for approximate counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q483707)