Advertisement
Published in:
2011 | OriginalPaper | Chapter
A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
Authors : Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Martin, Vojtěch Rödl, Asaf Shapira
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The Frieze-Kannan regularity lemma is a powerful tool in combinatorics. It has also found applications in the design of approximation algorithms and recently in the design of fast combinatorial algorithms for boolean matrix multiplication. The algorithmic applications of this lemma require one to efficiently construct a partition satisfying the conditions of the lemma.
Williams [24] recently asked if one can construct a partition satisfying the conditions of the Frieze-Kannan regularity lemma in deterministic sub-cubic time. We resolve this problem by designing an
$\tilde O(n^{\omega})$
time algorithm for constructing such a partition, where
ω
< 2.376 is the exponent of fast matrix multiplication. The algorithm relies on a spectral characterization of vertex partitions satisfying the properties of the Frieze-Kannan regularity lemma.