Journal article icon

Journal article

CLAP: A new algorithm for promise CSPs

Abstract:

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by a...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1137/22M1476435

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Jesus College
Role:
Author
ORCID:
0000-0002-0263-159X
More from this funder
Name:
Royal Society
Grant:
UF120013
More from this funder
Name:
European Commission
Grant:
714532
Publisher:
Society for Industrial and Applied Mathematics
Journal:
SIAM Journal on Computing More from this journal
Volume:
52
Issue:
1
Pages:
1-37
Publication date:
2023-01-25
Acceptance date:
2022-10-11
DOI:
EISSN:
1095-7111
ISSN:
0097-5397
Language:
English
Keywords:
Pubs id:
1282385
Local pid:
pubs:1282385
Deposit date:
2022-10-11

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP