The Taub Faculty of Computer Science Events and Talks

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