Understanding ReLU Networks Through Graph Problems and Polyhedra

While modern machine learning often relies on large and complex models, fundamental theoretical questions remain open even for simple architectures such as feedforward ReLU networks. For example, what is the precise set of (piecewise linear) functions representable by ReLU networks of a given depth? And which functions can be represented by neural networks of polynomial size? In this talk, I will present recent progress towards resolving these questions, using tools from polyhedral geometry, graph theory, and combinatorial optimization.