8 citations · 19 across the 13 of their papers we have counts for
25 papers
Cookie cutters: Bisections with fixed shapes
Patrick Schnider, Pablo Soberón
In a mass partition problem, we are interested in finding equitable partitions of smooth measures in . In this manuscript, we study the problem of finding simultaneou…
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…
Decomposition of Geometric Graphs into Star Forests
János Pach, Morteza Saghafian, Patrick Schnider
We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on vertices cannot be decomposed into fewer than star-forests, each consi…
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…