The complexity of 3-colouring H-colourable graphs
- Submitting institution
-
University of Durham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 124108
- Type
- E - Conference contribution
- DOI
-
10.1109/FOCS.2019.00076
- Title of conference / published proceedings
- Foundations of Computer Science (FOCS)
- First page
- 1227
- Volume
- -
- Issue
- -
- ISSN
- 25758454
- Open access status
- Compliant
- Month of publication
- -
- Year of publication
- 2020
- URL
-
https://doi.org/10.1109/FOCS.2019.00076
- 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
-
1
- Research group(s)
-
B - Algorithms and Complexity
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The paper solves a half of a very difficult conjecture posed by Guruswami, a world-leading expert in complexity of approximation, jointly with his student Brakensiek (SODA'18). The paper combines, for the first time, methods from universal algebra and algebraic topology to answer questions about complexity of approximation. This methodology was subsequently used by Wrochna and Zivny (probably SODA'20).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -