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

Preprints

• On the Depth of Monotone ReLU Neural Networks and ICNNs. Egor Bakaev, Florestan Brunck, Christoph Hertrich, Daniel Reichman, and Amir Yehudayoff (2025). 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.
• 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.

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