About

Christoph Hertrich is a tenure-track professor for Applied Discrete Mathematics at the University of Technology Nuremberg. His research interests span various topics across discrete mathematics, theoretical computer science, and machine learning, with an emphasis on applying techniques from polyhedral geometry and combinatorial optimization to neural network theory.

Previously, in 2023/24, Prof. Hertrich was a postdoc at Université libre de Bruxelles advised by Prof. Samuel Fiorini and partially funded through a Marie Skłodowska-Curie fellowship. He paused his stay in Brussels when he acted as a substitute professor for discrete mathematics at Goethe-Universität Frankfurt in the winter semester 2023/24. Furthermore, in 2022/23, Prof. Hertrich was a postdoc with Prof. László Végh at LSE in London. He completed his PhD with Prof. Martin Skutella at TU Berlin (2018-22), and his B.Sc. and M.Sc. with Prof. Sven O. Krumke at TU Kaiserslautern (2013-18).

Selected Publications

• 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. International Conference on Learning Representations (ICLR 2025)
• 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. Conference on Integer Programming and Combinatorial Optimization (IPCO 2024).
• Tao, Y., Végh, L. A., & Hertrich, C. (2023). Mode connectivity in auction design. Conference on Neural Information Processing Systems Accepted for Mathematics of Operations Research (2025). Conference Version at Conference on Neural Information Processing Systems (NeurIPS 2023)
• Froese, V., & Hertrich, C. (2023). Training neural networks is NP-hard in fixed dimension. 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. 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. 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).

Full List of Pubications of Prof. Dr. Christoph Hertrich on Google Scholar