Source author record

Christoph Hertrich

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Discrete Mathematics Machine Learning math.CO Neural and Evolutionary Computing Data Structures and Algorithms

Catalog footprint

Research overview

3works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

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, non-equivalent definitions of what a linear region actually is. We systematically assess which papers use which definitions and discuss how they relate to each other. We then analyze the computational complexity of counting the number of such regions for the various definitions. Generally, this turns out to be an intractable problem. We prove NP- and #P-hardness results already for networks with one hidden layer and strong hardness of approximation results for two or more hidden layers. Finally, on the algorithmic side, we demonstrate that counting linear regions can at least be achieved in polynomial space for some common definitions.

preprint2022arXiv

Coloring Drawings of Graphs

We consider cell colorings of drawings of graphs in the plane. Given a multi-graph $G$ together with a drawing $Γ(G)$ in the plane with only finitely many crossings, we define a cell $k$ -coloring of $Γ(G)$ to be a coloring of the maximal connected regions of the drawing, the cells, with $k$ colors such that adjacent cells have different colors. By the $4$ -color theorem, every drawing of a bridgeless graph has a cell $4$ -coloring. A drawing of a graph is cell $2$ -colorable if and only if the underlying graph is Eulerian. We show that every graph without degree 1 vertices admits a cell $3$ -colorable drawing. This leads to the natural question which abstract graphs have the property that each of their drawings has a cell $3$ -coloring. We say that such a graph is universally cell $3$ -colorable. We show that every $4$ -edge-connected graph and every graph admitting a nowhere-zero $3$ -flow is universally cell $3$ -colorable. We also discuss circumstances under which universal cell $3$ -colorability guarantees the existence of a nowhere-zero $3$ -flow. On the negative side, we present an infinite family of universally cell $3$ -colorable graphs without a nowhere-zero $3$ -flow. On the positive side, we formulate a conjecture which has a surprising relation to a famous open problem by Tutte known as the $3$ -flow-conjecture. We prove our conjecture for subcubic and for $K_{3,3}$ -minor-free graphs.

preprint2022arXiv

The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality

Understanding the computational complexity of training simple neural networks with rectified linear units (ReLUs) has recently been a subject of intensive research. Closing gaps and complementing results from the literature, we present several results on the parameterized complexity of training two-layer ReLU networks with respect to various loss functions. After a brief discussion of other parameters, we focus on analyzing the influence of the dimension $d$ of the training data on the computational complexity. We provide running time lower bounds in terms of W[1]-hardness for parameter $d$ and prove that known brute-force strategies are essentially optimal (assuming the Exponential Time Hypothesis). In comparison with previous work, our results hold for a broad(er) range of loss functions, including $\ell^p$ -loss for all $p\in[0,\infty]$ . In particular, we extend a known polynomial-time algorithm for constant $d$ and convex loss functions to a more general class of loss functions, matching our running time lower bounds also in these cases.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.