Seth Pettie is a Professor of Computer Science and Engineering at University of Michigan. He received his Ph.D. in 2003 from the University of Texas at Austin, and was an Alexander von Humboldt Postdoctoral Fellow at MPI-Saarbrücken from 2003-2006. He has held visiting professor positions at Aarhus University (2013-14) and Bar-Ilan University (2023).

AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

A vertex connectivity oracle is a data structure that answers queries
of the form MIN{kappa(u,v), k}, 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.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

988 5655 4581

passcode not visible

logged in users only

If you wish to attend the talk but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.