Paper Info
Title
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT
Abstract
We show how to approximate any function in AC0 by decision trees of much smaller height than its number of variables. More precisely, we show that any function in n variables computable by an unbounded fan-in circuit of AND, OR, and NOT gates that has size S and depth d can be approximated by a decision tree of height n - βn to within error exp(-βn), where β = β(S, d) = 2-O(d log4/5 S). Our proof is constructive and we use its constructivity to derive a deterministic algorithm for #AC0 SAT with multiplicative factor savings over the naive 2n S algorithm of 2-Ω(βn), when applied to any n-input AC0 circuit of size S and depth d. Indeed, in the same running time we can deterministically construct a decision tree of size at most 2n-βn that exactly computes the function given by such a circuit. Recently, Impagliazzo, Matthews, and Paturi derived an algorithm for #AC0 SAT with greater savings over the naive algorithm but their algorithm is only randomized rather than deterministic. The main technical result we prove to show the above is that for every family F of k-DNF formulas in n variables and every 1 <; C = C(n) ≤ logpoly(k) |F|, one can construct a distribution on restrictions that each set at most n/C variables such that, except with probability at most 2-n/(2O(k)Clog |T|), after application of the restriction, all formulas in F simultaneously reduce to logpoly(k) |F|-juntas where an s-junta is a function whose value depends on only s of its inputs. Previously, Ajtai showed simultaneous approximations for k-DNF formulas by juntas related to the one we show but with a dependence on exp(k) rather than poly(k), resulting in a weaker height-approximation tradeoff than ours.
Year
DOI
Venue
2012
10.1109/CCC.2012.40
IEEE Conference on Computational Complexity
Keywords
Field
DocType
approximation theory,circuit complexity,computability,decision trees,deterministic algorithms,logic gates,probability,#AC0SAT,2n S algorithm,AC0 approximation,AND gates,NOT gates,OR gates,deterministic algorithm,k-DNF formulas,logpoly(k) |F|-juntas,multiplicative factor savings,n-input AC0 circuit,probability,satisfiability algorithm,small height decision trees,unbounded fan-in circuit,Constant-depth circuits,Decision trees,Satisfiability algorithms
Decision tree,Discrete mathematics,Logic gate,Combinatorics,Multiplicative function,Circuit complexity,Constructive,Approximation theory,Computability,Deterministic algorithm,Mathematics
Conference
ISSN
ISBN
Citations 
1093-0159
978-1-4673-1663-7
2
PageRank 
References 
Authors
0.37
5
3
Name
Order
Citations
PageRank
Paul Beame12234176.07
Russell Impagliazzo25444482.13
Srikanth Srinivasan313221.31