19 citations · 67 across the 17 of their papers we have counts for
22 papers
Two Linear Programs are Better than One
Alexander E. Black, Christoph Hertrich, Stefan Kober +1
The extension complexity of a polytope is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural network…
Shallower ReLU Network Representations via Exact Linear Algebra
Kilian Rueß, Gennadiy Averkov, Florestan Brunck +7
We study the depth required by ReLU networks to exactly represent piecewise linear functions, focusing specifically on the maximum function. This problem has recently received sign…
Arithmetic Circuits and Neural Networks for Regular Matroids
Christoph Hertrich, Stefan Kober, Georg Loho
We prove that there exist uniform -circuits of size to compute the basis generating polynomial of regular matroids on elements. By tropicalization, this…
On the Depth of Monotone ReLU Neural Networks and ICNNs
Egor Bakaev, Florestan Brunck, Christoph Hertrich +2
We study two models of ReLU neural networks: monotone networks (ReLU) and input convex neural networks (ICNN). Our focus is on expressivity, mostly in terms of depth, and we pr…
The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
Moritz Stargalla, Christoph Hertrich, Daniel Reichman
An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different,…
Better Neural Network Expressivity: Subdividing the Simplex
Egor Bakaev, Florestan Brunck, Christoph Hertrich +2
This work studies the expressivity of ReLU neural networks with a focus on their depth. A sequence of previous works showed that hidden layers are suffi…
Depth-Bounds for Neural Networks via the Braid Arrangement
Moritz Grillo, Christoph Hertrich, Georg Loho
We contribute towards resolving the open question of how many hidden layers are required in ReLU networks for exactly representing all continuous and piecewise linear functions on…
Neural Networks and (Virtual) Extended Formulations
Christoph Hertrich, Georg Loho
Neural networks with piecewise linear activation functions, such as rectified linear units (ReLU) or maxout, are among the most fundamental models in modern machine learning. We ma…
Decomposition Polyhedra of Piecewise Linear Functions
Marie-Charlotte Brandenburg, Moritz Grillo, Christoph Hertrich
In this paper we contribute to the frequently studied question of how to decompose a continuous piecewise linear (CPWL) function into a difference of two convex CPWL functions. Eve…
A First Order Method for Linear Programming Parameterized by Circuit Imbalance
Richard Cole, Christoph Hertrich, Yixin Tao +1
Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs…
Mode Connectivity in Auction Design
Christoph Hertrich, Yixin Tao, László A. Végh
Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable eco…
Training Neural Networks is NP-Hard in Fixed Dimension
Vincent Froese, Christoph Hertrich
We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and l…
Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes
Christian Haase, Christoph Hertrich, Georg Loho
We prove that the set of functions representable by ReLU neural networks with integer weights strictly increases with the network depth while allowing arbitrary width. More precise…
Training Fully Connected Neural Networks is -Complete
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut +2
We consider the problem of finding weights and biases for a two-layer fully connected neural network to fit a given set of data points as well as possible, also known as EmpiricalR…
Towards Lower Bounds on the Depth of ReLU Neural Networks
Christoph Hertrich, Amitabh Basu, Marco Di Summa +1
We contribute to a better understanding of the class of functions that can be represented by a neural network with ReLU activations and a given architecture. Using techniques from…
The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Vincent Froese, Christoph Hertrich, Rolf Niedermeier
Understanding the computational complexity of training simple neural networks with rectified linear units (ReLUs) has recently been a subject of intensive research. Closing gaps an…
ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
Christoph Hertrich, Leon Sering
This paper studies the expressive power of artificial neural networks with rectified linear units. In order to study them as a model of real-valued computation, we introduce the co…
Coloring Drawings of Graphs
Christoph Hertrich, Felix Schröder, Raphael Steiner
We consider cell colorings of drawings of graphs in the plane. Given a multi-graph together with a drawing in the plane with only finitely many crossings, we define a ce…
Scheduling a Proportionate Flow Shop of Batching Machines
Christoph Hertrich, Christian Weiß, Heiner Ackermann +2
In this paper we study a proportionate flow shop of batching machines with release dates and a fixed number of machines. The scheduling problem has so far barely receive…
Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
Christoph Hertrich, Martin Skutella
The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this backgrou…
Online Algorithms to Schedule a Proportionate Flexible Flow Shop of Batching Machines
Christoph Hertrich, Christian Weiß, Heiner Ackermann +2
This paper is the first to consider online algorithms to schedule a proportionate flexible flow shop of batching machines (PFFB). The scheduling model is motivated by manufacturing…
Sweep Algorithms for the Capacitated Vehicle Routing Problem with Structured Time Window
Christoph Hertrich, Philipp Hungerländer, Christian Truden
The capacitated Vehicle Routing Problem with structured Time Windows (cVRPsTW) is concerned with finding optimal tours for vehicles with given capacity constraints to deliver goods…