New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs

Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami +2

In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain…