Theory Lunch Seminar - Tim Hsieh

— 1:00pm

Location:
In Person - Reddy Conference Room, Gates Hillmsan 4405

Speaker:
TIM HSIEH , Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://jthsieh.github.io/

Rounding Large Independent Sets on Expanders
In this talk, we will present a new approach for approximating large independent sets when the input graph is a one-sided spectral expander – that is, the uniform random walk matrix of the graph has the second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost 3-colorable or are promised to contain an independent set of size (1/2 - ε)n. Somewhat surprisingly, we observe that the analogous task of finding a linear-sized independent set in almost 4-colorable one-sided expanders (even when the second eigenvalue is o(1)) is NP-hard, assuming the Unique Games Conjecture.

Our rounding builds on the method of simulating multiple samples from a pseudodistribution introduced by Bafna et. al. for rounding Unique Games instances. The key to our analysis is a new clustering property of large independent sets in expanding graphs — every large independent set has a larger-than-expected intersection with some member of a small list— and its formalization in the low-degree sum-of-squares proof system.

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

Event Website:
https://www.cs.cmu.edu/~theorylunch/

Add event to Google
Add event to iCal