An efficient regularity concept for sparse graphs and matrices

Let A be a 0/1 matrix of size m x n, and let p be the density of A (i.e., the number of ones divided by m · n). We show that A can be approximated in the cut norm within ε · mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m · n of A, provided that A satisfies a certain boundedness condition. The decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan (Combinatorica 1999) to sparse matrices. As an application, we obtain efficient 1 - ε approximation algorithms for "bounded" instances of Max CSP problems.20