6 citations · 6 across the 4 of their papers we have counts for
9 papers
Near-Linear Time Maximum Clique in Circular Arc Graphs
Dario Moschetti, Adam Polak, Jonas Schmidt
We present a near-linear time algorithm to find a maximum clique in circular arc graphs, the intersection graphs of arcs on the circumference of a circle, answering a 30-year-old o…
A Simple Algorithm for Counting Solutions to Integer Programs
Daniel Dadush, Anita Dürr, Thekla Hamm +2
We consider the problem of counting solutions to integer linear programming problems of the form where $A \in \{-Δ,\ldots,Δ\}^{m \times n…
3SUM Is Really Hard: A Real-to-Integer Reduction
Nick Fischer, Adam Polak, Jonas Schmidt
We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. Thi…
Warm-Starting All-Pairs Shortest Paths with Predictions
Adam Polak, Jonas Schmidt
One of the three key hypotheses of fine-grained complexity asserts that computing All-Pairs Shortest Paths (APSP) requires cubic time, up to subpolynomial factors, in the worst cas…
A Parameterized Study of Secluded Structures in Directed Graphs
Jonas Schmidt, Shaily Verma, Nadym Mallek
Given an undirected graph and an integer , the Secluded -Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property and has at most $…
How to Reduce Temporal Cliques to Find Sparse Spanners
Sebastian Angrick, Ben Bals, Tobias Friedrich +7
Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the edge set may change over time, but these changes are known in advance. This be…
Dynamic constant time parallel graph algorithms with sub-linear work
Jonas Schmidt, Thomas Schwentick
The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant time and work on the CRCW PRAM model. Th…
Counting Horizontal Visibility Graphs
Martina Juhnke-Kubitzke, Daniel Köhne, Jonas Schmidt
Horizontal visibility graphs (HVGs, for short) are a common tool used in the analysis and classification of time series with applications in many scientific fields. In this article…
Local Grand Unification in the Heterotic Landscape
Jonas Schmidt
We consider the possibility that the unification of the electroweak interactions and the strong force arises from string theory, at energies significantly lower than the string sca…