Thesis
Promise constraint satisfaction problems
- Abstract:
-
The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists under the strict constraints, the task is to find a solution under the weak constraints.
Austrin, Guruswami, and Hastad [SICOMP’17] showed that the problem of...
Expand abstract
Actions
Access Document
- Files:
-
-
(Preview, Dissemination version, pdf, 761.3KB, Terms of use)
-
Authors
Contributors
+ Zivny, S
- Institution:
- University of Oxford
- Division:
- MPLS
- Department:
- Computer Science
- Role:
- Supervisor
- ORCID:
- 0000-0002-0263-159X
+ Jeavons, P
- Role:
- Examiner
- ORCID:
- 0000-0003-4333-8506
+ Krokhin, A
- Role:
- Examiner
+ Natural Sciences and Engineering Research Council of Canada
More from this funder
- Funder identifier:
- http://dx.doi.org/10.13039/501100000038
- Funding agency for:
- Brandts-Longtin, A
- Grant:
- PGSD3-519582-2018
- Programme:
- NSERC Postgraduate Scholarships – Doctoral program
+ European Research Council
More from this funder
- Funding agency for:
- Brandts-Longtin, A
- Zivny, S
- Grant:
- 714532
- DOI:
- Type of award:
- DPhil
- Level of award:
- Doctoral
- Awarding institution:
- University of Oxford
- Language:
-
English
- Keywords:
- Subjects:
- Deposit date:
-
2022-12-05
- ARK identifier:
Terms of use
- Copyright holder:
- Alexandre Brandts-Longtin
- Copyright date:
- 2022
- Rights statement:
- © Author(s) 2022
If you are the owner of this record, you can report an update to it here: Report update to this record