{"id":"arxiv/2607.21651","url":"https://arxiv.org/abs/2607.21651","tags":["cs.LG","cs.NE","math.CO"],"score":0,"title":"Shallower ReLU Network Representations via Exact Linear Algebra","domain":"cs.LG","source":"arxiv","authors":["Kilian Rueß","Gennadiy Averkov","Florestan Brunck","Moritz Grillo","Christoph Hertrich","Georg Loho","Jack Stade","Moritz Stargalla","Matthew Sun","Martin Winter"],"reviews":0,"subject":"cs.LG","summary":"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 significant attention in both the ML and TCS literature. We prove that $\\max_n(x)=\\max\\{x_1,\\ldots,x_n\\}$ is exactly representable with two hidden layers for every $n\\leq 12$. Previously, this was only known up to $n\\leq5$ [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. We obtain our constructions through an exact computer-assisted search within a space of candidate solutions: After a symmetry reduction, we…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-22","reactions":{}}