Arithmetic Circuits: A survey of recent results and open questions

By Amir Shpilka, Amir Yehudayoff. Foundations and Trends® in Theoretical Computer Science, 2010

501 citations recorded by the source corpus.

How researchers see this paper

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

On the Expressive Efficiency of Sum Product Networks (2014, background): “77 17 v1 [ cs .”
Understanding Deep Neural Networks with Rectified Linear Units (2016, background): “…of the function space represented by ReLU DNNs also takes inspiration from the classical theory of circuit complexity; we refer the reader to Arora & Barak (2009); Shpilka & Yehudayoff (2010); Jukna (2012); Saptharishi (2014); Allender (1998) for various surveys of this deep and fascinating field.”
On the Expressive Power of Deep Learning: A Tensor Analysis (2015, unknown): “More recent studies focus on arithmetic circuits (Shpilka and Yehudayoff (2010)), whose nodes typically compute either a weighted sum or a product of their inputs 9 (besides their role in studying expressiveness, deep networks of this class have been shown to support provably optimal training Livni…”
The Power of Depth for Feedforward Neural Networks (2015, background): “Moving to networks with real-valued outputs, one related ﬁeld is arithmetic circuit complexity (see Shpilka and Yehudayoff [2010] for a survey), but the focus there is on computing polynomials, which can be thought of as neural networks where each neuron computes a linear combination or a product…”