23 citations · 25 across the 6 of their papers we have counts for
9 papers
Shallower ReLU Network Representations via Exact Linear Algebra
Kilian Rueß, Gennadiy Averkov, Florestan Brunck +7
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 sign…
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…
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…
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…
Two Tiling is Undecidable
Jack Stade
We show that the following problem is undecidable: given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them. This improve…
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…
Humanity's Last Exam
Long Phan, Alice Gatti, Ziwen Han +1168
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…
The Point-Boundary Art Gallery Problem is -hard
Jack Stade
We resolve the complexity of the point-boundary variant of the art gallery problem, showing that it is -complete, meaning that it is equivalent under polynomial…
Topological Universality of the Art Gallery Problem
Jack Stade, Jamie Tucker-Foltz
We prove that any compact semi-algebraic set is homeomorphic to the solution space of some art gallery problem. Previous works have established similar universality theorems, but h…