Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Approximate Hypergraph Partitioning and Applications
event speaker icon
Asaf Shapira
event date icon
Sunday, 30.12.2007, 10:30
event location icon
Room 337-8 Taub Bld.
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