Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)

We explicitly construct, for every integer n and ε ≫ 0, a family of functions (psuedo-random bit generators) fn, ε: {0, 1}nε → {0, 1}n with the following property: for a random seed, the pseudorandom output "looks random" to any polynomial size, constant depth, unbounded fan-in circuit. Moreover, the functions fn, ε themselves can be computed by uniform polynomial size, constant depth circuits. Some (interrelated) consequences of this result are given below. 1) Deterministic simulation of probabilistic algorithms. The constant depth analogues of the probabilistic complexity classes RP and BPP are contained in the deterministic complexity classes DSPACE(nε) and DTIME(2nε) for any ε ≫ 0. 2) Making probabilistic constructions deterministic. Some probablistic constructions of structures that elude explicit constructions can be simulated in the above complexity classes. 3) Approximate counting. The number of satisfying assignments to a (CNF or DNF) formula, if not too small, can be arbitrarily approximated in DSPACE(nε) and DTIME(2nε), for any ε ≫ 0. We also present two results for the special case of depth 2 circuits. They deal, respectively, with finding a satisfying assignment and approximately counting the number of assignments. For example, for 3-CNF formulas with a fixed fraction of satisfying assignmemts, both tasks can be performed in polynomial time!

Authors

• Miklós Ajtai
• Avi Wigderson

Keywords

• Circuit simulation
• Polynomials
• Computational modeling
• Random number generation
• Cryptography
• Frequency selective surfaces
• Buildings
• Analytical models
• Algorithm design and analysis
• Parallel algorithms
• Constant Depth
• Circuit Depth
• Constant-depth Circuits
• Random Variables
• Input Variables
• Complex Class
• Subset Of Variables
• Uniform Probability
• Proof Of The Lemma
• Pseudo-random Number Generator
• Random Bits
• Explicit Construction