8 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…
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…
The Planted Orthogonal Vectors Problem
David Kühnemann, Adam Polak, Alon Rosen
In the -Orthogonal Vectors (-OV) problem we are given sets, each containing binary vectors of dimension , and our goal is to pick one vector from each set…
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Jakob Nogler, Adam Polak, Barna Saha +3
The tree edit distance (TED) between two rooted ordered trees with nodes labeled from an alphabet is the minimum cost of transforming one tree into the other by a sequence…
3SUM in Preprocessed Universes: Faster and Simpler
Shashwat Kasliwal, Adam Polak, Pratyush Sharma
We revisit the 3SUM problem in the \emph{preprocessed universes} setting. We present an algorithm that, given three sets , , of integers, preprocesses them in quadrat…
Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
Bingbing Hu, Adam Polak
Most of the known tight lower bounds for dynamic problems are based on the Online Boolean Matrix-Vector Multiplication (OMv) Hypothesis, which is not as well studied and understood…
Connectivity Oracles for Predictable Vertex Failures
Bingbing Hu, Evangelos Kosinas, Adam Polak
The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous…
Deterministic 3SUM-Hardness
Nick Fischer, Piotr Kaliciak, Adam Polak
As one of the three main pillars of fine-grained complexity theory, the 3SUM problem explains the hardness of many diverse polynomial-time problems via fine-grained reductions. Man…