Algebraic approach to promise constraint satisfaction
- Submitting institution
-
University of Durham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 122348
- Type
- E - Conference contribution
- DOI
-
10.1145/3313276.3316300
- Title of conference / published proceedings
- ACM Symposium on Theory of Computing (STOC)
- First page
- 602
- Volume
- -
- Issue
- -
- ISSN
- 07378017
- Open access status
- Compliant
- Month of publication
- -
- Year of publication
- 2019
- URL
-
https://doi.org/10.1145/3313276.3316300
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
B - Algorithms and Complexity
- Citation count
- 9
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The content of this paper was the basis for some invited talks and tutorials, e.g. by Krokhin at Computational Complexity Conference (CCC'18) and by Barto at Fundamentals of Computation Theory (FCT'19). The full version of this paper has been invited to the special STOC'19 issue of SIAM Journal on Computing. Initial versions of results from the paper led to successful grant application to EPSRC (EP/R034516/1, 2018-21, ~441K). Follow-up papers using the theory developed here include Krokhin and Oprsal (FOCS'19), Kozik et al. (ICALP'19), Wrochna and Zivny (probably SODA'20).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -