Showing 2024Show all
3 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…
cs.CC2024
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…