8 papers
Shallower ReLU Network Representations via Exact Linear Algebra
Kilian RueÃ, Gennadiy Averkov, Florestan Brunck +7
We prove that the maximum of real numbers is exactly representable by a ReLU network with two hidden layers for every . The constructions are obtained by reducing the…
Probabilistically checkable proofs for the Existential Theory of the Reals
Jack Stade
We prove a PCP theorem for the existential theory of the reals, showing that MAX-ETR-INV is -hard to approximate to within some constant factor. The existential…
NP-membership for the boundary-boundary art-gallery problem
Jack Stade
The boundary-boundary art-gallery problem asks, given a polygon representing an art-gallery, for a minimal set of guards that can see the entire boundary of (the wall of th…
Humanity's Last Exam
Long Phan, Alice Gatti, Ziwen Han +1144
Benchmarks are important tools for tracking the rapid advancements in large language model (LLM) capabilities. However, benchmarks are not keeping pace in difficulty: LLMs now achi…
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…
Devil's Games and : Continuous Games complete for the First-Order Theory of the Reals
Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow +2
We introduce the complexity class Quantified Reals (). Let FOTR be the set of true sentences in the first-order theory of the reals. A language is in $\text…