Rounding Moment Based SDP Relaxations by Column Selection

Ali Kemal Sinop
Institute for Advanced Study; Member, School of Mathematics
October 8, 2013

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.

Concert Talks - Bruce Adolphe, Edward T. Cone Concert Series

Bruce Adolphe
Edward T. Cone Concert Series
October 13, 2013

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.

Obfuscating Programs Against Algebraic Attacks

Yael Tauman-Kalai
Microsoft Research New England
October 14, 2013

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.