Applied Discrete Mathematics Lab

Prof. Dr. Christoph Hertrich

The Applied Discrete Mathematics Lab combines fundamental research in discrete mathematics and theoretical computer science with applications in practically relevant fields like optimization and machine learning. A current focus of the lab is to advance the mathematical understanding of artificial neural networks using methods from polyhedral geometry and combinatorial optimization.

Prof. Dr. Christoph Hertrich
Professor for Applied Discrete Mathematics

Selected Publications

Grillo, M., Hertrich, C., & Loho, G. (2025) Depth-Bounds for Neural Networks via the Braid Arrangement. arXiv Preprint, arXiv:2502.09324v1
Hertrich, C., & Loho, G. (2024). Neural networks and (virtual) extended formulations. arXiv preprint, arXiv:2411.03006.
Brandenburg, M. C., Grillo, M., & Hertrich, C. (2024). Decomposition polyhedra of piecewise linear functions. (ICLR 2025). Spotlight (top 5 %)
Hertrich, C., & Sering, L. (2024). ReLU neural networks of polynomial size for exact maximum flow computation. Mathematical Programming, 1–30.
Cole, R., Tao, Y., Végh, L. A., & Hertrich, C. (2024). A first order method for linear programming parameterized by circuit imbalance. In Conference on Integer Programming and Combinatorial Optimization (IPCO 2024).
Tao, Y., Végh, L. A., & Hertrich, C. (2023). Mode connectivity in auction design. In Conference on Neural Information Processing Systems (NeurIPS 2023). Accepted for Mathematics of Operations Research (2025)
Froese, V., & Hertrich, C. (2023). Training neural networks is NP-hard in fixed dimension. In Conference on Neural Information Processing Systems (NeurIPS 2023).
Bertschinger, D., Jungeblut, P., Miltzow, T., Weber, S., & Hertrich, C. (2023). Training fully connected neural networks is ER-complete. In Conference on Neural Information Processing Systems (NeurIPS 2023).
Basu, A., Di Summa, M., Skutella, M., & Hertrich, C. (2023). Towards lower bounds on the depth of ReLU neural networks. SIAM Journal on Discrete Mathematics (SIDMA). Conference version at Conference on Neural Information Processing Systems (NeurIPS 2021).
Skutella, M., & Hertrich, C. (2023). Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS Journal on Computing (IJOC). Conference version at AAAI 2021 Conference on Artificial Intelligence.
Haase, C., Loho, G., & Hertrich, C. (2023). Lower bounds on the depth of integral ReLU neural networks via lattice polytopes. In International Conference on Learning Representations (ICLR 2023).
Froese, V., Niedermeier, R., & Hertrich, C. (2022). The computational complexity of ReLU network training parameterized by data dimensionality. Journal of Artificial Intelligence Research (JAIR).
Weiß, C., Ackermann, H., Heydrich, S., Krumke, S. O., & Hertrich, C. (2022). Online algorithms to schedule a proportionate flexible flow shop of batching machines. Journal of Scheduling (J Sched).
Schröder, F., Steiner, R., & Hertrich, C. (2022). Coloring drawings of graphs. Electronic Journal of Combinatorics (E-JC).