In this lecture, I will talk about moment based SDP hierarchies (which are duals of SOS relaxations for polynomial optimization) in the context of graph partitioning. The focus will be on a certain way of rounding such hierarchies, whose quality is related to the problem of column based matrix reconstruction. Finally I will describe how to relate this to the spectral or isoperimetric profiles of the underlying constraint graph.
The Edward T. Cone Concert Series season opened on Friday October 11 with Sight and Sound, featuring the celebrated Cassatt String Quartet. The program included a new work by Bruce Adolphe based on the life and paintings of Impressionist painter and printmaker Mary Cassat. In this video, Sebastian Currier, Artist-in-Residence, and Bruce Adolphe take the stage to discuss the concert.
The goal of (general-purpose) program obfuscation is to make an arbitrary computer program "unintelligible" while preserving its functionality. The problem of program obfuscation is well studied both in theory and in practice. Though despite its importance, until very recently, even heuristic constructions for general-purpose obfuscation were not known.