Fetching the paper…
Reading the bibliography…
When studying the expressive power of neural networks, a main challenge is to understand how the size and depth of the network affect its ability to approximate real functions.
Complexity classes in communication complexity theory
L. Babai, P. Frankl, and J. Simon · 1986
Earlier work this paper cites.
Approximation by superpositions of a sigmoidal function
G. Cybenko · 1989
Earlier work this paper cites.
On the approximate realization of continuous mappings by neural networks
K.-I. Funahashi · 1989
Earlier work this paper cites.
Approximation capabilities of multilayer feedforward networks
K. Hornik · 1991
Earlier work this paper cites.
On the computational power of sigmoid versus boolean threshold circuits
W. Maass, G. Schnitger, and E. D. Sontag · 1991
Earlier work this paper cites.
Majority gates vs. general weighted threshold gates
M. Goldmann, J. Håstad, and A. Razborov · 1992
Earlier work this paper cites.
The probabilistic communication complexity of set intersection
B. Kalyanasundaram and G. Schintger · 1992
Earlier work this paper cites.
A linear lower bound for the size of threshold circuits
H. D. Groeger and G. Turán · 1993
Earlier work this paper cites.
The communication complexity of threshold gates
N. Nisan · 1993
Earlier work this paper cites.
Approximation and estimation bounds for artificial neural networks
A. R. Barron · 1994
Earlier work this paper cites.
Lower bounds on threshold and related circuits via communication complexity
V. P. Roychowdhury, A. Orlitsky, and K.-Y. Siu · 1994
Earlier work this paper cites.
Vc dimension in circuit complexity
P. Koiran · 1996
Earlier work this paper cites.
Communication complexity
E. Kushilevitz and N. Nisan · 1997
Earlier work this paper cites.
Bounds for the computational power and learning complexity of analog neural nets
W. Maass · 1997
Earlier work this paper cites.
Natural proofs
A. A. Razborov and S. Rudich · 1997
Earlier work this paper cites.
Simulating threshold circuits by majority circuits
M. Goldmann and M. Karpinski · 1998
Earlier work this paper cites.
Interpolation by a game
J. Kraíček · 1998
Cited alongside, same era.
Pseudorandom functions in tc 0 {}^{\mbox{0}} and cryptographic limitations to proving lower bounds
M. Krause and S. Lucks · 2001
Cited alongside, same era.
An information statistics approach to data stream and communication complexity
Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar · 2004
Cited alongside, same era.
Number-theoretic constructions of efficient pseudo-random functions
M. Naor and O. Reingold · 2004
Cited alongside, same era.
Computational complexity: a modern approach
S. Arora and B. Barak · 2009
Cited alongside, same era.
Boolean function complexity: advances and frontiers , volume 27
S. Jukna · 2012
Cited alongside, same era.
Depth-width tradeoffs in approximating natural functions with neural networks
I. Safran and O. Shamir · 2017
Later among the works it cites.
Error bounds for approximations with deep relu networks
D. Yarotsky · 2017
Later among the works it cites.
Toward super-polynomial size lower bounds for depth-two threshold circuits
L. Chen · 2018
Later among the works it cites.
Optimal approximation of piecewise smooth functions using deep relu neural networks
P. Petersen and F. Voigtlaender · 2018
Later among the works it cites.
R. R. Williams · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
On the representational efficiency of restricted boltzmann machines
J. Martens, A. Chattopadhya, T. Pitassi, and R. Zemel · 2013
Cited alongside, same era.
Unconditional lower bounds in complexity theory
I. C. Oliveira · 2015
Cited alongside, same era.
How limited interaction hinders real communication (and what it means for proof and circuit complexity)
S. F. de Rezende, J. Nordström, and M. Vinyals · 2016
Cited alongside, same era.
The power of depth for feedforward neural networks
R. Eldan and O. Shamir · 2016
Cited alongside, same era.
A better-than-3n lower bound for the circuit complexity of an explicit function
M. G. Find, A. Golovnev, E. A. Hirsch, and A. S. Kulikov · 2016
Cited alongside, same era.
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
D. M. Kane and R. Williams · 2016
Cited alongside, same era.
D. Yarotsky · 2018
Later among the works it cites.
Equality alone does not simulate randomness
A. Chattopadhyay, S. Lovett, and M. Vinyals · 2019
Later among the works it cites.
Depth separations in neural networks: What is actually being separated?
I. Safran, R. Eldan, and O. Shamir · 2019
Later among the works it cites.
Deep network approximation characterized by number of neurons
Z. Shen, H. Yang, and S. Zhang · 2019
Later among the works it cites.
The phase diagram of approximation rates for deep neural networks
D. Yarotsky and A. Zhevnerchuk · 2019
Later among the works it cites.
Sharp representation theorems for relu networks with precise dependence on depth
G. Bresler and D. Nagaraj · 2020
Later among the works it cites.
Expressivity of deep neural networks
I. Gühring, M. Raslan, and G. Kutyniok · 2020
Later among the works it cites.
Deep network approximation for smooth functions
J. Lu, Z. Shen, H. Yang, and S. Zhang · 2020
Later among the works it cites.
Neural networks with small weights and depth-separation barriers
G. Vardi and O. Shamir · 2020
Later among the works it cites.
The connection between approximation, depth separation and learnability in neural networks
E. Malach, G. Yehudai, S. Shalev-Shwartz, and O. Shamir · 2021
Closest in time.