366 citations · 2.5k across the 44 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2021★ 3 cited
Small Promise CSPs that reduce to large CSPs
Alexandr Kazda, Peter Mayr, Dmitriy Zhuk
For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A,B) asks whether a given input structure maps homomorphically to A or does n…
cs.CC2020★ 1 cited
Sandwiches for Promise Constraint Satisfaction
Guofeng Deng, Ezzeddine El Sai, Trevor Manders +3
Promise Constraint Satisfaction Problems (PCSP) were proposed recently by Brakensiek and Guruswami arXiv:1704.01937 as a framework to study approximations for Constraint Satisfacti…