AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Consider the following setting: There is some simple unknown graph G=(V,E). One has access to G only via queries known as *cut queries*, in which one can specify some subset S of V and obtain back the number of edges that cross the cut defined by S in G. A natural question to ask is what is the cut-query complexity of finding the minimum cut in the input graph. This is a special case of the well-known problem of sub-modular function minimization. Throughout the talk, we'll use this problem as a vehicle for exemplifying the usefulness of a novel simple combinatorial procedure, styled Star-Contraction. Namely, this tool allows us to obtain a randomized cut query protocol for the problem with O(n) cut queries. I'll then discuss additional applications of Star-Contraction and open problems.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

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