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 di...
Expand abstract
Actions
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
Funding
+ 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
+ European Research Council
More from this funder
Funding agency for:
Zivny, S
Brandts-Longtin, A
Grant:
714532
Bibliographic Details
- Type of award:
- DPhil
- Level of award:
- Doctoral
- Awarding institution:
- University of Oxford
Item Description
- Language:
- English
- Keywords:
- Subjects:
- Deposit date:
- 2022-12-05
Related Items
Terms of use
- Copyright holder:
- Alexandre Brandts-Longtin
- Copyright date:
- 2022
- Rights statement:
- © Author(s) 2022
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record