Showing 2026Show all
2 papers · 1 filter
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.DS2026
Computing Twin-Width via Treedepth and Vertex Integrity
Robert Ganian, Mathis Rocton
Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorith…