Shallower ReLU Network Representations via Exact Linear Algebra

Kilian Rueß, Gennadiy Averkov, Florestan Brunck, Moritz Grillo, Christoph Hertrich, Georg Loho, Jack Stade, Moritz Stargalla, Matthew Sun, Martin Winter

arXivarxiv/2607.21651Jul 22, 2026cs.LGscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2607.21651
curl -X POST /api/v1/records/arxiv/2607.21651/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.21651/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'