Image de couverture de livre

Training Neural Networks is NP-Hard in Fixed Dimension

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Froese, Vincent, Hertrich, Christoph
Format:	Preprint
Publié:	2023
Sujets:	Computational Complexity Data Structures and Algorithms Machine Learning Neural and Evolutionary Computing
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
par: Hertrich, Christoph, et autres
Publié: (2021)

Parameterized Hardness of Zonotope Containment and Neural Network Verification
par: Froese, Vincent, et autres
Publié: (2025)

Learning to Approximate Uniform Facility Location via Graph Neural Networks
par: Qian, Chendi, et autres
Publié: (2026)

Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
par: Bertschinger, Daniel, et autres
Publié: (2022)

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
par: Hertrich, Christoph, et autres
Publié: (2020)

Which Algorithms Can Graph Neural Networks Learn?
par: Wittig, Solveig, et autres
Publié: (2026)

Convergence Analysis for Deep Sparse Coding via Convolutional Neural Networks
par: Li, Jianfei, et autres
Publié: (2024)

Multi-Neuron Representations of Hierarchical Concepts in Spiking Neural Networks
par: Lynch, Nancy A.
Publié: (2024)

Predictive Spike Timing Enables Distributed Shortest Path Computation in Spiking Neural Networks
par: Storesund, Simen, et autres
Publié: (2025)

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
par: Stargalla, Moritz, et autres
Publié: (2025)

Covered Forest: Fine-grained generalization analysis of graph neural networks
par: Vasileiou, Antonis, et autres
Publié: (2024)

Convergence and Running Time of Time-dependent Ant Colony Algorithms
par: Manthey, Bodo, et autres
Publié: (2025)

Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints
par: Liu, Dan-Xuan, et autres
Publié: (2024)

A Scalable Trie Building Algorithm for High-Throughput Phyloanalysis of Wafer-Scale Digital Evolution Experiments
par: Singhvi, Vivaan, et autres
Publié: (2025)

Abstraction in Neural Networks
par: Lynch, Nancy
Publié: (2024)

Computational-Statistical Tradeoffs from NP-hardness
par: Blanc, Guy, et autres
Publié: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
par: Kleinberg, Robert, et autres
Publié: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
par: Guruswami, Venkatesan, et autres
Publié: (2023)

Hardness of Maximum Likelihood Learning of DPPs
par: Grigorescu, Elena, et autres
Publié: (2022)

On the Hardness of Approximation of the Fair k-Center Problem
par: Thejaswi, Suhas
Publié: (2026)

Hardness of Learning Boolean Functions from Label Proportions
par: Guruswami, Venkatesan, et autres
Publié: (2024)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
par: Gaikwad, Ajinkya, et autres
Publié: (2025)

How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
par: Doerr, Benjamin, et autres
Publié: (2023)

Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
par: Doerr, Benjamin, et autres
Publié: (2023)

The Runtime of Random Local Search on the Generalized Needle Problem
par: Doerr, Benjamin, et autres
Publié: (2024)

Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator
par: Bendahi, Abderrahim, et autres
Publié: (2025)

Hyper-Heuristics Can Profit From Global Variation Operators
par: Doerr, Benjamin, et autres
Publié: (2024)

Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
par: Doerr, Benjamin, et autres
Publié: (2022)

Sorting by Strip Swaps is NP-Hard
par: Roy, Swapnoneel, et autres
Publié: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
par: Nederlof, Jesper
Publié: (2026)

Prove Symbolic Regression is NP-hard by Symbol Graph
par: Song, Jinglu, et autres
Publié: (2024)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
par: Alman, Josh, et autres
Publié: (2024)

Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
par: Pintér, József, et autres
Publié: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
par: Dhawan, Abhishek, et autres
Publié: (2024)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

AdaBoost is not an Optimal Weak to Strong Learner
par: Høgsgaard, Mikael Møller, et autres
Publié: (2023)

Superconstant Inapproximability of Decision Tree Learning
par: Koch, Caleb, et autres
Publié: (2024)

Exact and Approximate Algorithms for Polytree Learning
par: Harviainen, Juha, et autres
Publié: (2026)

Differentially Private Verification of Distribution Properties
par: Du, Elbert, et autres
Publié: (2026)

Efficient and Private Property Testing via Indistinguishability
par: Dwork, Cynthia, et autres
Publié: (2025)