Yuval Efron, Columbia University

Abstract

In this talk I'll discuss a simple combinatorial randomized procedure, which is styled Star Contraction. Then, I'll discuss applications of this technical procedure, with the central one being a randomized cut query algorithm that with constant probability computes the edge connectivity of a simple graph with O(n) cut queries. I'll also discuss applications to quantum cut queries and the semi-streaming model. Finally, I'll talk about some interesting open problems.
Based on work which will appear in FOCS 2022