Conference item icon

Conference item

The complexity of general-valued CSPs seen from the other side

Abstract:

The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand side structures, the results of Dalmau, Kolaitis, and Vardi [CP'02], Grohe [FOCS'03/JACM'07], and Atserias, Bulatov, and Dalmau [ICALP'07] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equi...

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

Actions


Access Document


Files:
Publisher copy:
10.1109/FOCS.2018.00031

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Živný, S
Grant:
Research Fellowship
Publisher:
Institute of Electrical and Electronics Engineers Publisher's website
Journal:
IEEE Symposium on Foundations of Computer Science Journal website
Volume:
59
Pages:
236-246
Host title:
Symposium on Foundations of Computer Science
Publication date:
2018-12-03
Acceptance date:
2018-06-30
Event location:
Paris, France
DOI:
EISSN:
2575-8454
ISSN:
1523-8288
Source identifiers:
891704
ISBN:
9781538642306
Keywords:
Pubs id:
pubs:891704
UUID:
uuid:ff413201-3318-4d67-85ee-c933f463fa60
Local pid:
pubs:891704
Deposit date:
2018-07-30

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