Computational limitations of small-depth circuits

By J. Håstad. 1987

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

Training Very Deep Networks (2015, background): “Related observations hold for Boolean circuits [8, 9] and modern neural networks [10, 11, 12].”
Deep Networks with Stochastic Depth (2016, background): “Network depth is a major determinant of model expressiveness, both in theory [9, 10] and in practice [5, 7, 8].”
Benefits of Depth in Neural Networks (2016, methodology): “In this way, the result carries some resemblance to the random projection technique used in depth hierarchy theorems for boolean functions (Håstad, 1986; Rossman et al., 2015), as well as earlier techniques on complexities of multivariate sets (Vitushkin, 1955, 1959), albeit in an extremely primitiv”
The computational complexity of linear optics (2010, background): “ then (via a nonuniform, nondeterministic reduction) one could extract small constant-depth circuits for the 2n-bit Majority function, thereby violating the celebrated circuit lower bounds of H˚astad [54] and others. What made this surprising was that the 2n-bit Majorityfunction is #P-complete.10 In”
Representation Benefits of Deep Feedforward Networks (2015, background): “An early result showing the beneﬁts of depth is due to H˚astad (1986), who established, via an incredible proof, that boolean circuits consisting only of and gates and or gates require exponential size in order to approximate the parity function well.”
Pseudorandom Functions: Three Decades Later (2017, background): “Circuits in this class cannot compute linear functions unless they are very large [58, 138, 73].”
Why and when can deep-but not shallow-networks avoid the curse of dimensionality: A review (2016, methodology): “in Boolean functions can be “read out” from the terms of their Fourier expansion corresponding to “large” coefﬁcients, that is from a polynomial that approximates well the function. Classical results [36] about the depth-breadth tradeoff in circuits design show that deep circuits are more efﬁcient i”
Learning Real and Boolean Functions: When Is Deep Better Than Shallow (2016, background): “Classical results (Hastad, 1987) about the depth-breadth tradeoff in circuits design show that deep circuits are more efficient in representing certain Boolean functions than shallow circuits.”
Learning Functions: When Is Deep Better Than Shallow (2016, background): “…and 2. the sparse algorithm which learns a function by approximating its signiﬁcant coefﬁcients. functions that cannot be represented eﬃciently results ([Hastad, 1987]) about the depth-breadth in representing certain Boolean Decision lists and decision trees can be learned by algo-rithm 1.”
Automated Melanoma Recognition in Dermoscopy Images via Very Deep Residual Networks (2017, background): “depth is a key factor of model expressiveness for a long time [27], [28].”
Deep vs. shallow networks : An approximation theory perspective (2016, result): “As we mentioned in previous papers [21, 20] this deﬁnition, and in fact most of the previous results, can be specialized to the class of Boolean functions which map the Boolean cube into reals, yielding a number of known [10] and new results.”