3 papers
cs.CG2023
On the Complexity of Recognizing Nerves of Convex Sets
Patrick Schnider, Simon Weber
We study the problem of recognizing whether a given abstract simplicial complex is the -skeleton of the nerve of -dimensional convex sets in . We denote thi…
cs.CG2023
Reducing Nearest Neighbor Training Sets Optimally and Exactly
Josiah Rohrer, Simon Weber
In nearest-neighbor classification, a training set of points in with given classification is used to classify every point in : Every point gets the…
cs.DS2022
Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs
Simon Weber, Joel Widmer
Algorithms for finding the sink in Unique Sink Orientations (USOs) of the hypercube can be used to solve many algebraic and geometric problems, most importantly including the P-Mat…