This project is funded by an ERC Starting Grant. The project runs from 1 January 2017 through 30 June 2022 in the Department of Computer Science at the University of Oxford.

** Principal Investigator **

** Postdoctoral Research Fellows **

- Jakub Opršal, 20 December 2021 - 31 May 2022 (→ IST Austria)
- Lorenzo Ciardo, 31 December 2020 - 30 June 2022
- Caterina Viola, 15 April 2020 - 30 June 2022 (→ Charles University, Czechia)
- Shuai Shao, 2 November 2020 - 1 November 2021 (→ University of Edinburgh, UK)
- Michael Kompatscher, 1 October 2020 - 30 September 2021 (→ Charles University, Czechia)
- Balázs Mezei, 8 April 2020 - 7 April 2021 (→ finance)
- Marcin Wrochna, 3 December 2018 - 2 December 2020 (→ University of Warsaw, Poland)
- Miguel Romero, 23 May 2017 - 31 October 2019 (→ Adolfo Ibañez University, Chile)
- Clément Carbonnel, 1 March 2017 - 30 November 2018 (→ CNRS, France)

** DPhil Students **

- Tamio-Vesa Nakajima, 1 October 2021 - 30 June 2022
- Alexandre Brandts-Longtin, 1 October 2018 - 30 June 2022
- Jacob Focke, 1 October 2019 - 30 September 2020 (→ Helmholtz/MPI, Germany)
- Peter Fulla, 1 October 2017 - 30 September 2018 (→ JSPS Fellowship @ NII, Japan)

** Faculty Collaborators **

** Project Summary **

Convex relaxations, such as linear and semidefinite programming, constitute one of the most powerful techniques for designing efficient algorithms, and have been studied in theoretical computer science, operational research, and applied mathematics. We seek to establish the power convex relaxations through the lens of, and with the extensions of methods designed for, Constraint Satisfaction Problems (CSPs).

Our goal is twofold. First, to provide precise characterisations of the applicability of convex relaxations such as which problems can be solved by linear programming relaxations. Secondly, to derive computational complexity consequences such as for which classes of problems the considered algorithms are optimal in that they solve optimally everything that can be solved in polynomial time. For optimisation problems, we aim to characterise the limits of linear and semidefinite programming relaxations for exact, approximate, and robust solvability. For decision problems, we aim to characterise the limits of local consistency methods, one of the fundamental techniques in artificial intelligence, which strongly relates to linear programming relaxations.

Recent years have seen some remarkable progress on characterising the power of algorithms for a very important type of problems known as non-uniform constraint satisfaction problems and their optimisation variants. The ultimate goal of this project is to develop new techniques and establish novel results on the limits of convex relaxations and local consistency methods in a general setting going beyond the realm of non-uniform CSPs.

** Visitors **

- Marcin Kozik, 1 April 2022 - 30 June 2022
- Caterina Viola, 14-18 October 2019
- Andrei Krokhin and Jakub Opršal, 23-27 September 2019
- Florent Capelli and Stefan Mengel, 16-20 September 2019
- Peter Fulla, 27-31 June 2019
- Martin Cooper, 1-5 April 2019
- Martin Cooper, 22-25 January 2019
- Amanda Vidal, 26-30 November 2018
- Andrei Bulatov, 9-20 July 2018
- Monaldo Mastrolilli, 15-21 April 2018
- Jakub Bulín, 29 January - 2 February 2018
- Andrei Bulatov, 10-26 July 2017
- Martin Cooper, 10-27 July 2017
- Johan Thapper, 26 June - 7 July 2017
- Yuni Iwamasa, 8-19 May 2017

** Funding information **

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). Our papers and publicity reflect only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.

** Papers **

- Eden Pelleg and Stanislav Živný, Additive sparsification of CSPs, Proceedings of
**ESA'21**. - Benoît Larose and Petar Marković and Barnaby Martin and Daniël Palusma and Siani Smith and Stanislav Živný, QCSP on reflexive tournaments, Proceedings of
**ESA'21**. - Balázs Mezei, Marcin Wrochna, and Stanislav Živný, PTAS for sparse general-valued CSPs, Proceedings of
**LICS'21**. - Alex Brandts and Stanislav Živný, Beyond PCSP(1-in-3,NAE), Proceedings of
**ICALP'21**. doi:10.4230/LIPIcs.ICALP.2021.121 - Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Živný, Counting homomorphisms to K
_{4}-minor-free graphs, modulo 2, Proceedings of**SODA'21**. doi:10.1137/1.9781611976465.137 - Miguel Romero, Marcin Wrochna, and Stanislav Živný, Treewidth-pliability and PTAS for Max-CSPs, Proceedings of
**SODA'21**. doi:10.1137/1.9781611976465.29 - Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný, The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems,
**SICOMP**49(6), pp. 1232-1248, 2020. doi:10.1137/20M1312745 - Clément Carbonnel, Miguel Romero, and Stanislav Živný, Point-width and Max-CSPs,
**ACM TALG**16(4), Article No. 54, 2020. doi:10.1145/3409447 - Gregor Matl and Stanislav Živný, Using a min-cut generalisation to go beyond Boolean surjective VCSPs,
**Algorithmica**82, pp. 3492-3520, 2020. doi:10.1007/s00453-020-00735-1 - David Cohen, Martin Cooper, Artem Kaznatcheev, and Mark Wallace, Steepest ascent can be exponential in bounded treewidth problems,
**ORL**48(3), pp. 217-224, 2020. doi:10.1016/j.orl.2020.02.010 - Dušan Knop, Michał Pilipczuk, and Marcin Wrochna, Tight complexity lower bounds for integer linear programming with few constraints,
**ACM ToCT**12(3), Article No. 19, 2020. doi:10.1145/3397484 - Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný, The complexity of approximately counting retractions,
**ACM ToCT**12(3), Article No. 15, 2020. doi:10.1145/3397472 - Andrei Bulatov and Stanislav Živný, Approximate counting CSP seen from the other side,
**ACM ToCT**12(2), Article No. 11, 2020. doi:10.1145/3389390 - Silvia Butti and Stanislav Živný, Sparsification of binary CSPs,
**SIDMA**34(1), pp. 825-842, 2020. doi:10.1137/19M1242446 - Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, and Stanislav Živný, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin,
**JCSS**109, pp. 95-125, 2020. doi:10.1016/j.jcss.2019.12.003 - Pablo Barceló, Miguel Romero, and Thomas Zeume, A more general theory of static approximations for conjunctive queries,
**ToCS**64, pp. 916-964, 2020. doi:10.1007/s00224-019-09924-0 - David Cohen, Martin Cooper, Peter Jeavons, and Stanislav Živný, Galois connections for patterns: An algebra of labelled graphs, Proceedings of
**GKR'20**. doi:10.1007/978-3-030-72308-8_9 - Caterina Viola and Stanislav Živný, The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains, Proceedings of
**MFCS'20**. doi:10.4230/LIPIcs.MFCS.2020.85 - Alex Brandts, Marcin Wrochna, and Stanislav Živný, The complexity of promise SAT on non-Boolean domains, Proceedings of
**ICALP'20**. doi:10.4230/LIPIcs.ICALP.2020.17 - Michael Benedikt, Stanislav Kikot, Piotr Ostropolski-Nalewaja, and Miguel Romero, On monotonic determinacy and rewritability for recursive queries and views, Proceedings of
**PODS'20**. doi:10.1145/3375395.3387661 - Marcin Wrochna and Stanislav Živný, Improved hardness for H-colourings of G-colourable graphs, Proceedings of
**SODA'20**. doi:10.1137/1.9781611975994.86 - Marcin Wrochna, PACE solver description: Sallow: A heuristic algorithm for treedepth decompositions, Proceedings of
**IPEC'20**. doi:10.4230/LIPIcs.IPEC.2020.36 - Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Živný, A tractable class of binary VCSPs via M-convex intersection,
**ACM TALG**15(3), Article No. 44, 2019. doi:10.1145/3329862 - Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný, The complexity of counting surjective homomorphisms and compactions,
**SIDMA**33(2), pp. 1006-1043, 2019. doi:10.1137/17M1153182 - Clément Carbonnel, David Cohen, Martin Cooper, and Stanislav Živný, On singleton arc consistency for CSPs defined by monotone patterns,
**Algorithmica**81(4) pp. 1699-1727, 2019. doi:10.1007/s00453-018-0498-2 - David Cohen, Martin Cooper, Peter Jeavons, and Stanislav Živný, Binary constraint satisfaction problems defined by excluded topological minors,
**IC**264, pp. 12-31, 2019. doi:10.1016/j.ic.2018.09.013 - Peter Fulla and Hannes Uppman, and Stanislav Živný, The complexity of Boolean surjective general-valued CSPs,
**ACM ToCT**11(1), Article No. 4, 2019. doi:10.1145/3282429 - Andrei Bulatov and Stanislav Živný, Approximate counting CSP seen from the other side, Proceedings of
**MFCS'19**. doi:10.4230/LIPIcs.MFCS.2019.60 - Pablo Barceló, Diego Figueira, and Miguel Romero, Boundedness of Conjunctive Regular Path Queries , Proceedings of
**ICALP'19**. doi:10.4230/LIPIcs.ICALP.2019.104 - Clément Carbonnel, Miguel Romero, and Stanislav Živný, Point-width and Max-CSPs, Proceedings of
**LICS'19**. doi:10.1109/LICS.2019.8785660 - Eduard Eiben, Robert Ganian, Dušan Knop, Sebastian Ordyniak, Michał Pilipczuk, and Marcin Wrochna, Integer programming and incidence treedepth, Proceedings of
**IPCO'19**. doi:10.1007/978-3-030-17953-3_15 - Dušan Knop, Michał Pilipczuk, and Marcin Wrochna, Tight complexity lower bounds for integer linear programming with few constraints, Proceedings of
**STACS'19**. doi:10.4230/LIPIcs.STACS.2019.44 - Silvia Butti and Stanislav Živný, Sparsification of binary CSPs, Proceedings of
**STACS'19**. doi:10.4230/LIPIcs.STACS.2019.17 - Gregor Matl and Stanislav Živný, Beyond Boolean surjective VCSPs, Proceedings of
**STACS'19**. doi:10.4230/LIPIcs.STACS.2019.52 - Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný, The complexity of approximately counting retractions, Proceedings of
**SODA'19**. doi:10.1137/1.9781611975482.133 - Johan Thapper and Stanislav Živný, The limits of SDP relaxations for general-valued CSPs,
**ACM ToCT**10(3), Article No. 12, 2018. doi:10.1145/3201777 - Yuni Iwamasa, Kazuo Murota, and Stanislav Živný, Discrete convexity in joint winner property,
**DO**28 78-88, 2018. doi:10.1016/j.disopt.2018.01.001 - Clément Carbonnel, Miguel Romero, and Stanislav Živný, The complexity of general-valued CSPs seen from the other side, Proceedings of
**FOCS'18**. doi:10.1109/FOCS.2018.00031 - Miguel Romero, The tractability frontier of well-designed SPARQL queries, Proceedings of
**PODS'18**. doi:10.1145/3196959.3196973 - Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Živný, Beyond JWP: A tractable class of binary VCSPs via M-convex intersection, Proceedings of
**STACS'18**. 10.4230/LIPIcs.STACS.2018.39 - Clément Carbonnel, David Cohen, Martin Cooper, and Stanislav Živný, On singleton arc consistency for CSPs defined by monotone patterns, Proceedings of
**STACS'18**. doi:10.4230/LIPIcs.STACS.2018.19 - Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný, The complexity of counting surjective homomorphisms and compactions, Proceedings of
**SODA'18**. doi:10.1137/1.9781611975031.116 - Martin Cooper and Stanislav Živný, The power of arc consistency for CSPs defined by partially-ordered forbidden patterns,
**LMCS**13(4:26) 1-32, 2017. doi:10.23638/LMCS-13(4:26)2017 - David Cohen, Martin Cooper, Peter Jeavons, Andrei Krokhin, Robert Powell, and Stanislav Živný, Binarisation for valued constraint satisfaction problems,
**SIDMA**31(4) 2279-2300, 2017. doi:10.1137/16M1088107 - Johan Thapper and Stanislav Živný, The power of Sherali-Adams relaxations for general-valued CSPs,
**SICOMP**46(4) 1241-1279, 2017. doi:10.1137/16M1079245 - Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, and Stanislav Živný, Functional clones and expressibility of partition functions,
**TCS**687 11-39, 2017. doi:10.1016/j.tcs.2017.05.001 - Peter Fulla and Stanislav Živný, On planar valued CSPs,
**JCSS**87 104-118, 2017. doi:10.1016/j.jcss.2017.03.005 - Peter Fulla and Stanislav Živný, The complexity of Boolean surjective general-valued CSPs, Proceedings of
**MFCS'17**. doi:10.4230/LIPIcs.MFCS.2017.4 - Johan Thapper and Stanislav Živný, The limits of SDP relaxations for general-valued CSPs, Proceedings of
**LICS'17**. doi:1109/LICS.2017.8005087