Summer 2019

Approximating CSPs on HDXs, and applications to codes

Thursday, Jul. 25, 2019 10:00 am11:30 am PDT

Add to Calendar


Madhur Tulsiani


Room 116

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.