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

Society for Industrial and Applied Mathematics eBooks 2026

View at publisher
Authors: Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Henry Potechin, Stanislav Živný
DOI: 10.1137/1.9781611978971.145
Cited by: 0

Abstract

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:

Fields of Study & Subjects

Complexity and Algorithms in Graphs Risk and Portfolio Optimization Advanced Graph Theory Research

Publication details

Journal / source
Society for Industrial and Applied Mathematics eBooks
Pages
3965–3977
Publication date
1 January 2026
Language
EN