6 citations · 6 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…