Showing 2023Show all
2 papers · 1 filter
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…
cs.CC2023
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…