Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
Authors: Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, Simon Weber
NeurIPS 2023 | Conference 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 daniel.bertschinger@inf.ethz.ch; Christoph Hertrich Department of Mathematics London School of Economics and Political Science London, United Kingdom c.hertrich@lse.ac.uk; Paul Jungeblut Institute of Theoretical Informatics Karlsruhe Institute of Technology Karlsruhe, Germany paul.jungeblut@kit.edu; Tillmann Miltzow Department of Information and Computing Sciences Utrecht University Utrecht, The Netherlands t.miltzow@uu.nl; Simon Weber Department of Computer Science ETH Zurich Zurich, Switzerland simon.weber@inf.ethz.ch |
| 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. |