3 papers
cs.DS2025
Hardness of Dynamic Tree Edit Distance and Friends
Bingbing Hu, Jakob Nogler, Barna Saha
String Edit Distance is a more-than-classical problem whose behavior in the dynamic setting, where the strings are updated over time, is well studied. A single-character substituti…
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…
cs.DS2023
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…