Simon Lukas Weber

Last Name

Weber

First Name

Simon Lukas

ORCID

0000-0003-1901-3621

Show all metadata

Search Results

Publications 1 - 10 of 21

On Flipping Edge Sets in Unique Sink Orientations
Borzechowski, Michaela; Weber, Simon Lukas (2025)
Graphs and combinatorics
A Universal Construction for Unique Sink Orientations
Borzechowski, Michaela; Doolittle, Joseph; Weber, Simon Lukas (2022)
arXiv
Unique Sink Orientations (USOs) of cubes can be used to capture the combinatorial structure of many essential algebraic and geometric problems. For various structural and algorithmic questions, including enumeration of USOs and algorithm analysis, it is crucial to have systematic constructions of USOs. While some construction methods for USOs already exist, each one of them has some significant downside. Most of the construction methods have limited expressivity -- USOs with some desired properties cannot be constructed. In contrast, the phase flips of Schurr can construct all USOs, but the operation is not well understood. We were inspired by techniques from cube tilings of space; we expand upon existing techniques in the area to develop generalized rewriting rules for USOs. These rewriting rules are a new construction framework which can be applied to all USOs. The rewriting rules can generate every USO using only USOs of lower dimension. The effect of any specific rewriting rule on an USO is simple to understand. A special case of our construction produces a new elementary transformation of USOs, which we call a partial swap. We further investigate the relationship between partial swaps and phase flips and generalize partial swaps to phase swaps.
Realizability in Matoušek Unique Sink Orientations: Characterization and Complexity Gap
Gärtner, Bernd; Weber, Simon Lukas; Widmer, Joel (2025)
The Electronic Journal of Combinatorics
Various algebraic and geometric problems reduce to the sink-finding problem in unique sink orientations (USOs), which are orientations of the hypercube graph that have a unique sink in every subcube. A USO is called realizable if it can arise from applying one of these reductions. We study how realizability influences the query complexity of the sink-finding problem. To this end, we consider a specific subclass of USOs, the so-called Matou & scaron;ek USOs. The Matou & scaron;ek USOs are a family of USOs which are a translation of the LP-type problems used by Matou & scaron;ek to show that the Sharir-Welzl algorithm for LP-type problems may require at least subexponential time [Matou & scaron;ek, 1994]. G & auml;rtner showed that the Random Facet algorithm for USO sink-finding requires at least subexponentially many vertex evaluation queries on Matou & scaron;ek USOs, but at most quadratically many queries on realizable Matou & scaron;ek USOs [G & auml;rtner, 2002]. However, G & auml;rtner did not fully characterize this realizable subset. In this paper, we fully characterize the realizable subset of the Matou & scaron;ektype USOs (the USOs isomorphic to a Matou & scaron;ek USO) and also provide concrete realizations using instances of the P-Matrix Linear Complementarity Problem, basing our work on the so-called cyclic-P-matroids studied by Fukuda, Klaus, and Miyata. We further extend the results of Matou & scaron;ek and G & auml;rtner for the Random Facet algorithm to the query complexity of the sink-finding problem itself: we show that sink-finding is strictly easier on realizable Matou & scaron;ek-type USOs than on all Matou & scaron;ek-type USOs. We show that in the realizable case O(log2 n) queries suffice, while in general exactly n queries are needed.
Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
Lill, Jonas; Petrova, Kalina; Weber, Simon Lukas (2024)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least $m/2 + (n-1)/4$. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., $f(k)\cdot O(m)$. We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least $w(G)/2 + w_{MSF}(G)/4$, where w(G) denotes the total weight of G, and $w_{MSF}(G)$ denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., $f(k)\cdot O(m+n)$.
The Complexity of Recognizing Geometric Hypergraphs
Bertschinger, Daniel; El Maalouly, Nicolas; Kleist, Linda; et al. (2023)
Lecture Notes in Computer Science ~ Graph Drawing and Network Visualization
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 hypergraph $H=(V,E)$, each vertex $v\in V$ is associated with a point $p_v\in \mathbb{R}^d$ and each hyperedge $e\in E$ is associated with a connected set $s_e\subset \mathbb{R}^d$ such that $\{p_v\mid v\in V\}\cap s_e=\{p_v\mid v\in e\}$ for all $e\in E$. We say that a given hypergraph $H$ is representable by some (infinite) family $F$ of sets in $\mathbb{R}^d$, if there exist $P\subset \mathbb{R}^d$ and $S \subseteq F$ such that $(P,S)$ is a geometric representation of $H$. For a family F, we define RECOGNITION(F) as the problem to determine if a given hypergraph is representable by F. It is known that the RECOGNITION problem is $\exists\mathbb{R}$-hard for halfspaces in $\mathbb{R}^d$. We study the families of translates of balls and ellipsoids in $\mathbb{R}^d$, as well as of other convex sets, and show that their RECOGNITION problems are also $\exists\mathbb{R}$-complete. This means that these recognition problems are equivalent to deciding whether a multivariate system of polynomial equations with integer coefficients has a real solution.
On the Complexity of Recognizing Nerves of Convex Sets
Schnider, Patrick; Weber, Simon Lukas (2023)
Computing in Geometry and Topology
We study the problem of recognizing whether a given abstract simplicial complex K is the k-skeleton of the nerve of j-dimensional convex sets in Rᵈ. We denote this problem by R(k, j, d). As a main contribution, we unify the results of many previous works under this framework and show that many of these works in fact imply stronger results than explicitly stated. This allows us to settle the complexity status of R(1, j, d), which is equivalent to the problem of recognizing intersection graphs of j-dimensional convex sets in Rᵈ, for any j and d. Furthermore, we point out some trivial cases of R(k, j, d), and demonstrate that R(k, j, d) is ER-complete for j in {d - 1, d} and k ≥ d.
Topological Art in Simple Galleries
Bertschinger, Daniel; El Maalouly, Nicolas; Miltzow, Tillmann; et al. (2024)
Discrete & Computational Geometry
Let P be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in P. We say two points a, b ∈ P can see each other if the line segment seg(a, b) is contained in P. We denote by V(P) the family of all minimum guard placements. The Hausdorff distance makes V(P) a metric space and thus a topological space. We show homotopy-universality, that is, for every semi-algebraic set S there is a polygon P such that V(P) is homotopy equivalent to S. Furthermore, for various concrete topological spaces T, we describe instances I of the art gallery problem such that V(I) is homeomorphic to T.
Topological Art in Simple Galleries
Bertschinger, Daniel; El Maalouly, Nicolas; Miltzow, Tillmann; et al. (2022)
Symposium on Simplicity in Algorithms (SOSA)
Let P be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in P. We say two points a, b ∊ P can see each other if the line segment seg(a, b) is contained in P. We denote by V (P) the family of all minimum guard placements. The Hausdorff distance makes V(P) a metric space and thus a topological space. We show homotopy-universality, that is for every semi-algebraic set S there is a polygon P such that V(P) is homotopy equivalent to S. Furthermore, for various concrete topological spaces T, we describe instances I of the art gallery problem such that V(I) is homeomorphic to T.
Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
Bertschinger, Daniel; Hertrich, Christoph; Jungeblut, Paul; et al. (2024)
Advances in Neural Information Processing Systems 36
We consider the algorithmic problem of finding the optimal weights and biases for a two-layer fully connected neural network to fit a given set of data points. This problem is known as empirical risk minimization in the machine learning community. We show that the problem is $\exists\mathbb{R}$-complete. This complexity class can be defined as the set of algorithmic problems that are polynomial-time equivalent to finding real roots of a polynomial with integer coefficients. Furthermore, we show that arbitrary algebraic numbers are required as weights to be able to train some instances to optimality, even if all data points are rational. Our results hold even if the following restrictions are all added simultaneously. $\bullet$ There are exactly two output neurons. $\bullet$ There are exactly two input neurons. $\bullet$ The data has only 13 different labels. $\bullet$ The number of hidden neurons is a constant fraction of the number of data points. $\bullet$ The target training error is zero. $\bullet$ The ReLU activation function is used. This shows that even very simple networks are difficult to train. The result explains why typical methods for $\mathsf{NP}$-complete problems, like mixed-integer programming or SAT-solving, cannot train neural networks to global optimality, unless $\mathsf{NP}=\exists\mathbb{R}$. We strengthen a recent result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021].
On connectivity in random graph models with limited dependencies
Lengler, Johannes; Martinsson, Anders; Petrova, Kalina; et al. (2024)
Random Structures & Algorithms

Publications 1 - 10 of 21

Simon Lukas Weber

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results