3 papers
cs.LG2026
New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
Cornelius Brand, Robert Ganian, Mathis Rocton
In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networ…
cs.CC2025
A Structural Complexity Analysis of Hierarchical Task Network Planning
Cornelius Brand, Robert Ganian, Fionn Mc Inerney +1
We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an…
cs.GT2024
The Complexity of Optimizing Atomic Congestion
Cornelius Brand, Robert Ganian, Subrahmanyam Kalyanasundaram +1
Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various a…