TIME: 1:30-2:20 pm,  March 11, 2008

PLACE: CSE 503  

SPEAKER: Asaf Shapira
         Microsoft Research

TITLE: Approximate Hypergraph Partitioning and Applications


ABSTRACT:
I will describe an O(n) time algorithmic version of Szemerdi's
regularity lemma. Unlike all the previous approaches for this
problem, which proved the lemma "algorithmically", and only
guaranteed to find partitions of tower-size, our algorithm will
find a small regular partition in the graph in the case that one
exists.  The algorithm can be extended to an O(n) time algorithmic
version of the hypergraph regularity lemma for k-uniform hypergraphs,
improving over the previous O(n^{2k-1}) algorithms.

The main tool we develop for the above algorithms is an algorithm
for finding approximate partitions of hypergraphs, which significantly
generalizes an algorithm of Goldreich-Goldwasser-Ron for finding
approximate partitions of graphs.

Joint work with Eldar Fischer and Arie Matsliach