10 citations · 25 across the 10 of their papers we have counts for
7 papers · 1 filter
A Topological Version of Schaefer's Dichotomy Theorem
Patrick Schnider, Simon Weber
Schaefer's dichotomy theorem [Schaefer, STOC'78] states that a boolean constraint satisfaction problem (CSP) is polynomial-time solvable if one of six given conditions holds for ev…
An FPT Algorithm for Splitting a Necklace Among Two Thieves
Michaela Borzechowski, Patrick Schnider, Simon Weber
It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the PPA-completeness…
On Connectivity in Random Graph Models with Limited Dependencies
Johannes Lengler, Anders Martinsson, Kalina Petrova +4
For any positive edge density , a random graph in the Erdős-Renyi model is connected with non-zero probability, since all edges are mutually independent. We consider r…
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…
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…
On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
Michaela Borzechowski, Simon Weber
Klaus showed that the Oriented Matroid Complementarity Problem (OMCP) can be solved by a reduction to the problem of sink-finding in a unique sink orientation (USO) if the input is…
The Complexity of Recognizing Geometric Hypergraphs
Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist +2
As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a geometric representation of a hyp…