Computer Science/Discrete Mathematics Seminar I

In this talk, we will present a new approach for approximating large independent sets when the input graph is a one-sided expander—that is, the uniform random walk matrix of the graph has second eigenvalue bounded away from 1. Specifically, we show a polynomial time algorithm that can find linear-sized independent sets in one-sided expanders that are almost $3$-colorable or promised to contain a $0.499n$-sized independent set.

All prior algorithms that beat the worst-case guarantees for the problem rely on bottom eigenspace enumeration techniques, which build on a classical work of Alon and Kahale and require two-sided expansion (i.e., bounded number of negative eigenvalues of magnitude close to 1). Such techniques provably fail in our setting because in contrast to bottom eigenspace enumeration that naturally extends to $k$-colorable graphs for any fixed constant $k$, we observe that finding linear-sized independent sets in almost $4$-colorable expanding graphs (as opposed to almost $3$-colorable graphs in our algorithmic result above) is NP-hard assuming the Unique Games Conjecture.

Our algorithms rely on a new framework for rounding sum-of-squares relaxations of the independent set problem based on a combinatorial approximate packing property—in any graph that satisfies one-sided spectral expansion (in fact, a weaker vertex expansion property suffices), the total number of large independent sets with small pairwise intersections is small.

Based on joint work with Mitali Bafna and Pravesh K. Kothari.