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
Version:
Accepted Manuscript

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 Division
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Zivny, S
Publisher:
Institute of Electrical and Electronics Engineers Publisher's website
Volume:
59
Pages:
236-246
Publication date:
2018-12-03
Acceptance date:
2018-06-30
DOI:
EISSN:
2575-8454
ISSN:
1523-8288
Pubs id:
pubs:891704
URN:
uri:ff413201-3318-4d67-85ee-c933f463fa60
UUID:
uuid:ff413201-3318-4d67-85ee-c933f463fa60
Local pid:
pubs:891704
ISBN:
9781538642306

Terms of use


Metrics


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