Almost optimal lower bounds for small depth circuits

By J. Håstad. 1986

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Better Mixing via Deep Representations (2012, background): “specific function families have shown that choosing a sufficient depth of representation can yield exponential benefits, in terms of size of the model, to represent some functions (H̊astad, 1986; H̊astad and Goldmann, 1991; Bengio et al., 2006; Bengio and LeCun, 2007; Bengio and Delalleau, 2011).”
Practical Recommendations for Gradient-Based Training of Deep Architectures (2012, background): “Complexity theory of circuits, e.g. (H˚astad, 1986; H˚astad and Goldmann, 1991), (which include neural networks as special cases) has much preceded the recent research on deep learning.”
The Power of Depth for Feedforward Neural Networks (2015, background): “To exemplify this, a classical result on Boolean circuits states that the parity function over {0, 1}d cannot be computed by constant-depth Boolean circuits whose size is polynomial in d (see for instance Håstad [1986]).”
On the Complexity of Neural Network Classifiers: A Comparison Between Shallow and Deep Architectures (2014, unknown): “In this ambit, it has been shown that there exist boolean functions, whose realization requires a polynomial number of logic gates ( AND , OR , and NOT ) using a network with l layers, whereas an exponential number of gates is needed for a smaller number of layers [40], [41].”
Exploring Strategies for Training Deep Neural Networks (2009, background): “Some families of functions which can be represented with a depth k circuit are such that they require an exponential number of logic gates to be represented by a depth k − 1 circuit (Håstad, 1986).”
Understanding Deep Neural Networks with Rectified Linear Units (2016, result): “In particular, our gap results are inspired by results like the ones by Hastad [13], Razborov [27] and Smolensky [36] which show a strict separation of complexity classes.”
On the Expressive Power of Deep Architectures (2011, background): “Theoretical results (Yao, 1985; H̊astad, 1986; H̊astad and Goldmann, 1991; Bengio et al., 2006; Bengio and Delalleau, 2011; Braverman, 2011), reviewed briefly here (see also a previous discussion by Bengio and LeCun, 2007b) suggest that in order to learn the kind of complicated functions that can re”
Complexity-Theoretic Foundations of Quantum Supremacy Experiments (2016, unknown): “pBPPTQBF and SampBQPTQBF become SampPSPACE (i.e., the class of approximate sampling problems solvable in polynomial space). An oracle Osuch that PHOis inﬁnite: a line of works by Yao [Yao85], Hastad [Has86], and others˚ constructed relativized worlds where PH is inﬁnite, and a very recent breakthrou”
Why Does Deep and Cheap Learning Work So Well? (2016, background): “Certain deep Boolean circuit networks are exponentially costly to flatten [39].”
Unsupervised Feature Learning and Deep Learning: A Review and New Perspectives (2012, background): “Theoretical results clearly show families of functions where a deep representation can be exponentially more efﬁcient than one that is insufﬁciently deep (H˚astad, 1986; H˚astad and Goldmann, 1991; Bengio et al. , 2006a; Bengio and LeCun, 2007; Bengio and Delalleau, 2011).”