Leírás
Abstract:
A vertex connectivity oracle is a data structure that
answers queries of the form MIN{kappa(u,v), k+1}, where kappa(u,v) is
the vertex connectivity between u and v, i.e., queries are answered
precisely up to the threshold k. In this talk I'll prove an
information-theoretic lower bound of Omega(kn) on the space complexity
of vertex connectivity oracles. This bound is tight, up to logarithmic
factors, and settles a long-standing question on whether
vertex-connectivity is more complex than edge-connectivity. (The talk
will take a tour through several erroneous theorems of Schnorr'79,
Gusfield-Naor'90, and Benczur'95, who made the opposite claim, that
vertex-connectivity information could be encoded in O(n log n) bits.)
We also give an improvement to the Izsak-Nutov vertex connectivity
oracle. It occupies space O(kn log n), answers queries in O(log n)
time, and is constructible in the time of poly(k) maximum flows.
Joint work with Thatchaphol Saranurak and Longhui Yin (STOC 2022).
arXiv:2201.00408.
Zoom link: https://zoom.us/j/2961946869