New algorithms and hardness results for robust satisfiability of (promise) CSPs

Conference item

In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023), and obtain the following results:

For the PCSP 1-in-3-SAT vs NAE-SAT with negations, we prove that it is hard, under the Unique Games conjecture (UGC), to satisfy 1 − Ω(1/ log(1/ϵ)) constraints in a (1 − ϵ)- satisfiable instance. This shows that the exponential loss incurred by the BGS algorithm for the case of Alternating-Threshold polymorphisms is necessary, in contrast to the polynomial loss achievable for Majority polymorphisms. For any Boolean PCSP that admits Majority polymorphisms, we give an algorithm satisfying 1 − O( √ ϵ) fraction of the weaker constraints when promised the existence of an assignment satisfying 1 − ϵ fraction of the stronger constraints. This significantly generalizes the Charikar–Makarychev–Makarychev algorithm for 2-SAT, and matches the optimal trade-off possible under the UGC. The algorithm also extends, with the loss of an extra log(1/ϵ) factor, to PCSPs on larger domains with a certain structural condition, which is implied by, e.g., a family of Plurality polymorphisms. We prove that assuming the UGC, robust satisfiability is preserved under the addition of equality constraints. As a consequence, we can extend the rich algebraic techniques for decision/search PCSPs to robust PCSPs. The methods involve the development of a correlated and robust version of the general SDP rounding algorithm for CSPs due to (Brown-Cohen, Raghavendra, ICALP 2016), which might be of independent interest.

Authors: Brakensiek, J; Ciardo, L; Guruswami, V; Potechin, A; Živný, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
• Pages: 3965-3977
• Publication date: 2026-01-07
• Acceptance date: 2025-10-03
• Event title: ACM-SIAM Symposium on Discrete Algorithms (SODA 2026)
• Event location: Vancouver, Canada
• Event website: https://www.siam.org/conferences-events/siam-conferences/soda26/
• Event start date: 2026-01-11
• Event end date: 2026-01-14
• DOI: 10.1137/1.9781611978971.145
• ISBN: 9781611978971
• Language: English