On Small Depth Threshold Circuits

By Alexander A. Razborov. 1992

Subfields: Algorithms & Complexity

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

1. Oriol Vinyals
2. Ilya Sutskever
3. Dale Schuurmans
4. Xinhua Zhang
5. Ozlem Aslan
6. Quoc V. Le
7. Andrew Gordon Wilson

Citations in the corpus

• Sequence to Sequence Learning with Neural Networks (2014, background): “A surprising example of the power of DNNs is their ability to sort N N -bit numbers using only 2 hidden layers of quadratic size [27].”
• Convex Deep Learning via Normalized Kernels (2014, background): “The IP problem is motivated by a fundamental result in the circuit complexity literature: any small weights threshold circuit of depth 2 requires size exp(Ω(n)) to compute (27) [39, 40].”