research
∙
07/07/2023
A Topological Version of Schaefer's Dichotomy Theorem
Schaefer's dichotomy theorem [Schaefer, STOC'78] states that a boolean c...
share
research
∙
06/26/2023
An FPT Algorithm for Splitting a Necklace Among Two Thieves
It is well-known that the 2-Thief-Necklace-Splitting problem reduces to ...
research
∙
02/28/2023
On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
We investigate degeneracy in the P-Matroid Oriented Matroid Complementar...
research
∙
02/27/2023
The Complexity of Recognizing Geometric Hypergraphs
As set systems, hypergraphs are omnipresent and have various representat...
research
∙
02/26/2023
On the Complexity of Recognizing Nerves of Convex Sets
We study the problem of recognizing whether a given abstract simplicial ...
research
∙
02/04/2023
Reducing Nearest Neighbor Training Sets Optimally and Exactly
In nearest-neighbor classification, a training set P of points in ℝ^d wi...
research
∙
11/11/2022
A Universal Construction for Unique Sink Orientations
Unique Sink Orientations (USOs) of cubes can be used to capture the comb...
research
∙
07/13/2022
Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs
Algorithms for finding the sink in Unique Sink Orientations (USOs) of th...
research
∙
04/27/2022
Power Bundle Adjustment for Large-Scale 3D Reconstruction
We present the design and the implementation of a new expansion type alg...
research
∙
04/04/2022
Training Fully Connected Neural Networks is ∃ℝ-Complete
We consider the algorithmic problem of finding the optimal weights and b...
research
∙
10/08/2021
Multidirectional Conjugate Gradients for Scalable Bundle Adjustment
We revisit the problem of large-scale bundle adjustment and propose a te...
research
∙
09/08/2021
A Characterization of the Realizable Matoušek Unique Sink Orientations
The Matoušek LP-type problems were used by Matoušek to show that the Sha...
research
∙
08/09/2021
Topological Art in Simple Galleries
Let P be a simple polygon, then the art gallery problem is looking for a...
research
∙
12/18/2019