Applied Discrete Mathematics

Preprints

• Optimized Qubit Routing for Commuting Gates via Integer Programming. Moritz Stargalla and Friedrich Wagner (2025). Preprint.
• On the Depth of Monotone ReLU Neural Networks and ICNNs. Egor Bakaev, Florestan Brunck, Christoph Hertrich, Daniel Reichman, and Amir Yehudayoff (2025). Preprint.
• An Adaptive Variable Neighborhood Search for a Family of Set Covering Routing Problems with an Application in Disaster Relief Operations. Andreas Hagn, Jan Krause, Moritz Stargalla, and Lorenza Moreno (2024). Preprint.
• Neural Networks and (Virtual) Extended Formulations. Christoph Hertrich and Georg Loho (2024). Preprint.

Publications

• Better Neural Network Expressivity: Subdividing the Simplex. Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff. Accepted to Symposium on Theory of Computing (STOC 2026). Preprint.
• Arithmetic Circuits and Neural Networks for Regular Matroids. Christoph Hertrich, Stefan Kober, and Georg Loho. Accepted to Conference on Integer Programming and Combinatorial Optimization (IPCO 2026). Preprint.
• Parameterized Hardness of Zonotope Containment and Neural Network Verification. Vincent Froese, Moritz Grillo, Christoph Hertrich, and Moritz Stargalla. International Conference on Learning Representations (ICLR 2026). Conference Version. Preprint.
• Neural Network Acceleration of Iterative Methods for Nonlinear Schrödinger Eigenvalue Problems. Daniel Peterseim, Jan-F. Pietschmann, Jonas Püschel, and Kilian Rueß. Journal of Computational and Applied Mathematics (2026). Journal Version. Preprint.
• Depth-Bounds for Neural Networks via the Braid Arrangement. Moritz Grillo, Christoph Hertrich, and Georg Loho. Accepted as Oral (top 77 of 21575 submissions) at Conference on Neural Information Processing Systems (NeurIPS 2025). Preprint.
• The Computational Complexity of Counting Linear Regions in ReLU Neural Networks. Moritz Stargalla, Christoph Hertrich, and Daniel Reichman. Conference on Neural Information Processing Systems (NeurIPS 2025). Conference Version. Preprint.
• A First Order Method for Linear Programming Parameterized by Circuit Imbalance. Richard Cole, Christoph Hertrich, Yixin Tao, and László A. Végh. Mathematical Programming (2025). Conference version at Conference on Integer Programming and Combinatorial Optimization (IPCO 2024). Journal Version. Conference Version. Preprint.
• Decomposition Polyhedra of Piecewise Linear Functions. Marie-Charlotte Brandenburg, Moritz Grillo, and Christoph Hertrich. Spotlight (top 5 %) at International Conference on Learning Representations (ICLR 2025). Conference Version. Preprint.
• Mode Connectivity in Auction Design. Christoph Hertrich, Yixin Tao, and László A. Végh. Mathematics of Operations Research (2025). Conference version at Conference on Neural Information Processing Systems (NeurIPS 2023). Journal Version. Conference Version. Preprint.
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation. Christoph Hertrich and Leon Sering. Mathematical Programming (2025). Conference version at Conference on Integer Programming and Combinatorial Optimization (IPCO 2023). Journal Version. Conference Version. Preprint.
• Training Neural Networks is NP-Hard in Fixed Dimension. Vincent Froese and Christoph Hertrich. Conference on Neural Information Processing Systems (NeurIPS 2023). Conference Version. Preprint.
• Training Fully Connected Neural Networks is ∃ℝ-Complete. Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Conference on Neural Information Processing Systems (NeurIPS 2023). Conference Version. Preprint.
• Towards Lower Bounds on the Depth of ReLU Neural Networks. Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. SIAM Journal on Discrete Mathematics (2023). Conference version at Conference on Neural Information Processing Systems (NeurIPS 2021). Journal Version. Conference Version. Preprint. Video.
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size. Christoph Hertrich and Martin Skutella. INFORMS Journal on Computing (2023). Conference version at AAAI Conference on Artificial Intelligence (AAAI 2021). Journal Version. Conference Version. Preprint. Video.
• Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes. Christian Haase, Christoph Hertrich, and Georg Loho. International Conference on Learning Representations (ICLR 2023). Conference Version. Preprint.
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality. Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. Journal of Artificial Intelligence Research (2022). Journal Version. Preprint.
• Online Algorithms to Schedule a Proportionate Flexible Flow Shop of Batching Machines. Christoph Hertrich, Christian Weiß, Heiner Ackermann, Sandy Heydrich, and Sven O. Krumke. Journal of Scheduling (2022). Journal Version. Preprint.
• Coloring Drawings of Graphs. Christoph Hertrich, Felix Schröder, and Raphael Steiner. Electronic Journal of Combinatorics (2022). Journal Version. Preprint.
• Scheduling a Proportionate Flow Shop of Batching Machines. Christoph Hertrich, Christian Weiß, Heiner Ackermann, Sandy Heydrich, and Sven O. Krumke. Journal of Scheduling (2020). Journal Version. Preprint.
• Decision Support for Material Procurement. Heiner Ackermann, Erik Diessel, Michael Helmling, Christoph Hertrich, Neil Jami, and Johanna Schneider. Operations Research Proceedings (2019). Conference Version.
• Sweep Algorithms for the Capacitated Vehicle Routing Problem with Structured Time Windows. Christoph Hertrich, Philipp Hungerländer, and Christian Truden. Operations Research Proceedings (2018). Conference Version. Preprint.