13 citations · 28 across the 13 of their papers we have counts for
3 papers · 1 filter
Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams +1
A recent and active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk…
Hollow Heaps
Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan +1
We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take…
Subtree Isomorphism Revisited
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen +2
The Subtree Isomorphism problem asks whether a given tree is contained in another given tree. The problem is of fundamental importance and has been studied since the 1960s. For som…