Campus Event Calendar

Event Entry

What and Who

Optimal Vertex Connectivity Oracles

Seth Pettie
University of Michigan
AG1 Mittagsseminar (own work)

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  
AG Audience

Date, Time and Location

Thursday, 2 March 2023
60 Minutes
Virtual talk
Virtual talk


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).


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

988 5655 4581
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 02/28/2023 08:59
Roohani Sharma, 02/15/2023 13:08
Roohani Sharma, 02/14/2023 22:36
Roohani Sharma, 01/30/2023 15:16 -- Created document.