110. Mathematical Colloquium

Uri Feige

Weizman Institute, Israel

ON RAMSEY MULTIPLICITIES AND HALF-RAMSEY GRAPHS

Wednesday December 5, 2018, 11:00
aula (refektar), 1st floor
MFF UK, Malostranské nám. 25, Praha 1

Abstract

We present a deterministic algorithm that computes the edge-connectivity of a graph in near-linear time. This is for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. Our algorithm is easily extended to find a concrete minimum edge-cut. In fact, we can construct the classic cactus representation of all minimum cuts in near-linear time.

The previous fastest deterministic algorithm by Gabow from STOC'91 took O(m + k^2 n), where k is the edge connectivity, but k could be as big as n-1.

At STOC'96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm and compare sizes.

Our main technical contribution is a near-linear time algorithm that contract vertex sets of a simple input graph G with minimum degree d, producing a multigraph with O(m/d) edges which preserves all minimum cuts of G with at least 2 vertices on each side.

In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.

About the speaker

Uriel (Uri) Feige studoval na Technionu a na Weizmanově institutu, kde získal v roce 1992 doktorát. Poté byl postdokem na předních institucích (IBM Yorktown Heights, Princeton University) a posléze byl zaměstnán na Weizmanově institutu, od roku 2003 jako řádný profesor. Delší dobu působil v prestižní Theory Group, Microsoft Research.

Aktivita prof. Feigeho je rozsáhlá a pokrývá v podstatě celou teoretickou infor matiku a příbuzné oblasti kombinatoriky, náhodných struktur a diskrétní geometrie. Vysoká úroveň jeho činnosti byla oceněna opakovaně na mezinárodní úrovni, zmiňme zde pouze Gödelovu cenu (2001) a zvanou přednášku na Mezinárodním kongresu matematiků (2002). Uri Feige je však velmi aktivní v mezinárodním kontextu, což dokládá skutečnost, že byl v programovúch výborech vpodstatě všech významných mezinárodních konferencí v oblasti teoretické informatiky.