4 papers
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…
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…
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…
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…