Computer Science/Discrete Mathematics Seminar II

I will discuss some recent results showing that the sum-of-squares SDP hierarchy can be used to find approximately optimal solutions to k-CSPs, provided that the instance satisfies certain expansion properties. These properties can be shown to follow from (k-1)-dimensional spectral expansion, but are in fact weaker and also present (for example) in instances where each constraint corresponds to a length-k walk in an expanding graph. I will also discuss applications to unique and list decoding of direct sum and direct product codes. Based on joint works with Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana and Shashank Shrivastava.