Abstract
Threshold weight, margin complexity, and MajorityofThreshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the measure, but there may exist Boolean circuits of depth three that have essentially maximal complexity exp(Theta(n)). However, existing techniques are far from showing this: for all three measures, the best lower bound for depth three circuits is exp(Omega(n^{2/5})). Moreover, prior methods exclusively study blockcomposed functions. Such methods appear intrinsically unable to prove lower bounds better than exp(Omega(sqrt{n})) even for depth four circuits, and have yet to prove lower bounds better than exp(Omega(sqrt{n})) for circuits of any constant depth.
We take a step toward showing that all of these complexity measures indeed exhibit a chasm at depth three. Specifically, for any arbitrarily small constant delta > 0, we exhibit a depth three circuit of polynomial size (in fact, an O(log n)decision list) of complexity exp(Omega(n^{1/2delta})) under each of these measures.
Our methods go beyond the blockcomposed functions studied in prior work, and hence may not be subject to the same barriers. Accordingly, we suggest natural candidate functions that may exhibit stronger bounds.
BibTeX  Entry
@InProceedings{bun_et_al:LIPIcs:2018:9439,
author = {Mark Bun and Justin Thaler},
title = {{Approximate Degree and the Complexity of Depth Three Circuits}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {35:135:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9439},
URN = {urn:nbn:de:0030drops94390},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.35},
annote = {Keywords: approximate degree, communication complexity, learning theory, polynomial approximation, threshold circuits}
}
Keywords: 

approximate degree, communication complexity, learning theory, polynomial approximation, threshold circuits 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) 
Issue Date: 

2018 
Date of publication: 

13.08.2018 