Fetching the paper…
Reading the bibliography…
Given a neural network, training data, and a threshold, it was known that it is NP-hard to find weights for the neural network such that the total error is below the threshold.
Some algebraic and geometric computations in PSPACE
John Canny · 1988
Earlier work this paper cites.
On the complexity of loading shallow neural networks
Stephen Judd · 1988
Earlier work this paper cites.
On the complexity of polyhedral separability
Nimrod Megiddo · 1988
Earlier work this paper cites.
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties
Nicolai Mnëv · 1988
Earlier work this paper cites.
Stretchability of pseudolines is NP-hard
Peter W. Shor · 1991
Earlier work this paper cites.
Training a 3-node neural network is NP-complete
Avrim L. Blum and Ronald L. Rivest · 1992
Earlier work this paper cites.
The identity problem for elementary functions and constants
Dan Richardson and John Fitch · 1994
Earlier work this paper cites.
Realization spaces of 4-polytopes are universal
Jürgen Richter-Gebert and Günter M. Ziegler · 1995
Earlier work this paper cites.
The computational intractability of training sigmoidal neural networks
L. K. Jones · 1997
Earlier work this paper cites.
Training a sigmoidal node is hard
Don R. Hush · 1999
Earlier work this paper cites.
Training a single sigmoidal neuron is hard
Jiří Šíma · 2002
Earlier work this paper cites.
Improved dense packings of congruent squares in a square
Thierry Gensane and Philippe Ryckelynck · 2005
Earlier work this paper cites.
Complexity of some geometric and topological problems
Marcus Schaefer · 2009
Earlier work this paper cites.
Tight hardness results for training depth-2 ReLU networks, 2020
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman · 2011
Earlier work this paper cites.
Integer realizations of disk and segment graphs
Colin McDiarmid and Tobias Müller · 2013
Cited alongside, same era.
Intersection graphs of segments and ∃ ℝ \exists\mathbb{R} , 2014
Jiří Matoušek · 2014
Cited alongside, same era.
Computational geometry column 62
Jean Cardinal · 2015
Cited alongside, same era.
ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod · 2015
Cited alongside, same era.
Who needs crossings? Hardness of plane graph rigidity
Zachary Abel, Erik Demaine, Martin Demaine, Sarah Eisenstat, Jayson Lynch, and Tao Schardl · 2016
Cited alongside, same era.
A catalog of ∃ 𝕣 \exists\mathbb{r} -complete decision problems about Nash equilibria in multi-player games
Training deep neural networks with 8-bit floating point numbers
Naigang Wang, Jungwook Choi, Daniel Brand, Chia-Yu Chen, and Kailash Gopalakrishnan · 2018
Later among the works it cites.
Learning two layer rectified neural networks in polynomial time
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff · 2019
Later among the works it cites.
A universality theorem for nested polytopes
Michael Gene Dobbins, Andreas Holmsen, and Tillmann Miltzow · 2019
Later among the works it cites.
A framework for ∃ ℝ \exists\mathbb{R} -completeness of two-dimensional packing problems
Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth · 2020
Later among the works it cites.
Complexity of training ReLU neural network
Digvijay Boob, Santanu S. Dey, and Guanghui Lan · 2020
Later among the works it cites.
Approximation algorithms for training one-node ReLU neural networks
Santanu S. Dey, Guanyi Wang, and Yao Xie · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Vittorio Bilò and Marios Mavronicolas · 2016
Cited alongside, same era.
A universality theorem for nonnegative matrix factorizations
Yaroslav Shitov · 2016
Cited alongside, same era.
Irrational guards are sometimes needed
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow · 2017
Cited alongside, same era.
Globally optimal gradient descent for a ConvNet with Gaussian inputs
Alon Brutzkus and Amir Globerson · 2017
Cited alongside, same era.
Intersection graphs of rays and grounded segments
Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber · 2017
Cited alongside, same era.
∀ ∃ ℝ \forall\exists\mathbb{R} -completeness and area-universality
Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rza̧żewski · 2017
Cited alongside, same era.
The art gallery problem is ∃ ℝ \exists\mathbb{R} -complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow · 2018
Cited alongside, same era.
Later among the works it cites.
Smoothing the gap between np and er
Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow · 2020
Later among the works it cites.
Optimal continual learning has perfect memory and is NP-hard
Jeremias Knoblauch, Hisham Husain, and Tom Diethe · 2020
Later among the works it cites.
Covering polygons is even harder
Mikkel Abrahamsen · 2021
Closest in time.
Geometric embeddability of complexes is ∃ ℝ \exists\mathbb{R} -complete
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow · 2021
Closest in time.
Incidence geometry in the projective plane via almost-principal minors of symmetric matrices
Tobias Boege · 2021
Closest in time.
The computational complexity of relu network training parameterized by data dimensionality
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier · 2021
Closest in time.
On classifying continuous constraint satisfaction problems
Tillmann Miltzow and Reinier F. Schmiermann · 2021
Closest in time.