Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That is, such distributions are very far from each other. We strengthen their result, and show that the distance is in fact exponentially close to one. This allows us to strengthen the parameters in their application for data structure lower bounds for succinct data structures for codes. From a technical point of view, we develop new large deviation bounds for functions computed by small depth decision trees, which we then apply to obtain bounds for AC0 circuits via the switching lemma. We show that if such functions are Lipschitz on average in a certain sense, then they are in fact Lipschitz almost everywhere. This type of result falls into the extensive line of research which studies large deviation bounds for the sum of random variables, where while not independent, exhibit large deviation bounds similar to these obtained by independent random variables.

Authors

• Christopher Beck
• Russell Impagliazzo
• Shachar Lovett

Keywords

• Vegetation
• Decision trees
• Hamming weight
• Noise
• Data structures
• Random variables
• Complexity theory
• Large Differences
• Decision Tree
• Uniform Distribution
• Small Trees
• Independent Random Variables
• Technical Point Of View
• Statistical Distance
• General Case
• Forest Trees
• Tree Height
• Codeword
• Binary Tree
• Boolean Variable
• Hyperacusis
• Good Set
• Random Input
• Small Height
• Collection Of Trees
• Balanced Tree
• Decision Forest
• Output Bits
• Small depth circuits
• Lower Bounds
• Sampling Distributions
• Concentration Bounds