Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
Authors: Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, Simon Weber
NeurIPS 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that the problem is R-complete. This complexity class can be defined as the set of algorithmic problems that are polynomial-time equivalent to finding real roots of a multivariate polynomial with integer coefficients. |
| Researcher Affiliation | Academia | Daniel Bertschinger Department of Computer Science ETH Zurich Zurich, Switzerland EMAIL; Christoph Hertrich Department of Mathematics London School of Economics and Political Science London, United Kingdom EMAIL; Paul Jungeblut Institute of Theoretical Informatics Karlsruhe Institute of Technology Karlsruhe, Germany EMAIL; Tillmann Miltzow Department of Information and Computing Sciences Utrecht University Utrecht, The Netherlands EMAIL; Simon Weber Department of Computer Science ETH Zurich Zurich, Switzerland EMAIL |
| Pseudocode | No | The paper provides high-level descriptions of its proof strategy and 'gadgets' in Section 6 'Proof Ideas' but does not include formal pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not describe software implementations or release source code. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with actual datasets. It refers to 'data points' in the context of defining the theoretical problem TRAIN-F2NN, but does not use or provide a public dataset for empirical training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical data splits (training, validation, test sets). |
| Hardware Specification | No | The paper is theoretical and does not describe any empirical experiments or the hardware used to conduct them. |
| Software Dependencies | No | The paper is theoretical and does not describe any software implementations or their dependencies. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore no experimental setup details like hyperparameters or training configurations are provided. |