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

** Principal Investigator **

** Postdoctoral Research Fellows **

- Michael Kompatscher, from 1 October 2020
- Caterina Viola, from 15 April 2020
- Balázs Mezei, from 8 April 2020
- Marcin Wrochna, from 3 December 2018
- 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 **

- Alexandre Brandts-Longtin, from 1 October 2018
- Jacob Focke, 1 October 2019 - 30 September 2020 (→ MPI, Germany)
- Peter Fulla, 1 October 2017 - 30 September 2018 (→ JSPS Fellowship @ NII, Japan)

** 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 **

- 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 **

- David A. Cohen, Martin C. 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 - Alex Brandts, Marcin Wrochna, and Stanislav Živný, The complexity of promise SAT on non-Boolean domains, Proceedings of
**ICALP(A)'20**. - Marcin Wrochna and Stanislav Živný, Improved hardness for H-colourings of G-colourable graphs, Proceedings of
**SODA'20**. doi:10.1137/1.9781611975994.86 - Pablo Barceló, Miguel Romero, and Thomas Zeume, A more general theory of static approximations for conjunctive queries,
**ToCS**2019. doi:10.1007/s00224-019-09924-0 - 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, Martinc 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, Martinc 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(B)'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