Computer Science Speaking Skills Talk
Speaker
SAI SANDEEP PALLERLA
Ph.D. Student
Computer Science Department
Carnegie Mellon University
When
-
Where
In Person
Description
Promise Constraint Satisfaction Problems(PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where we allow each predicate to have a strong and a weak form. They are versatile and capture optimization problems such as approximate graph coloring that are not captured by the traditional CSPs. In this work, we study robust algorithms for PCSPs i.e., algorithms that output solution satisfying 1-f(epsilon) fraction of the constraints when the instance is guaranteed to have a solution satisfying 1-epsilon fraction of constraints, where f(epsilon) goes to 0 as epsilon goes to 0.
Our main result is a dichotomy result for Boolean Symmetric folded PCSPs, showing that they admit a robust algorithm if and only if they contain Majority or Alternating-Threshold family of polymorphisms assuming the Unique Games Conjecture. Our algorithms are based on rounding SDPs, and our hardness result is obtained by obtaining integrality gap for the standard SDP relaxation and using Raghavendra's framework to then get Unique Games based hardness.
Based on Joint work with Joshua Brakensiek and Venkatesan Guruswami.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.