You are here

Computer Science/Discrete Mathematics Seminar II

Approximating CSPs on expanding structures, and applications to codes

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.


Madhur Tulsiani

Speaker Affiliation

Toyota Technological Institute at Chicago



Event Series

Date & Time
January 21, 2020 | 10:30am12:30pm


Simonyi Hall 101