Power of Algorithms in Discrete Optimisation (PoweAlgDO)

Power of Algorithms in Discrete Optimisation (PowAlgDO)

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

Principal Investigator

Standa Živný

Postdoctoral Research Fellows

Jakub Opršal, 20 December 2021 – 31 May 2022 (→ IST Austria)
Lorenzo Ciardo, 31 December 2020 – 30 June 2022 (→ NAASP)
Caterina Viola, 15 April 2020 – 30 June 2022 (→ Charles University, Czechia)
Shuai Shao, 2 November 2020 – 1 November 2021 (→ USTC, China)
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 (→ PUC, Chile)
Clément Carbonnel, 1 March 2017 – 30 November 2018 (→ CNRS, France)

DPhil Students

Tamio-Vesa Nakajima, 1 October 2021 – 30 June 2022 (→ NAASP)
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

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

Clément Carbonnel, Miguel Romero, and Stanislav Živný, The complexity of general-valued CSPs seen from the other side, SICOMP 49(6), pp. 1232–1248, 2022. doi:10.1137/19M1250121
Benoît Larose, Petar Marković, Barnaby Martin, Daniël Palusma, Sani Smith,and Stanislav Živný, QCSP on reflexive tournaments, ACM ToCL 23(3), Article No. 14, 2022. doi:10.1145/3508069
Tamio-Vesa Nakajima and Stanislav Živný, Linearly ordered colourings of hypergraphs, Proceedings of ICALP'22. doi:10.4230/LIPIcs.ICALP.2022.128
Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Živný, Approximately counting answers to conjunctive queries with disequalities and negations, Proceedings of PODS'22. doi:10.1145/3517804.3526231
Lorenzo Ciardo and Stanislav Živný, CLAP: A new algorithm for promise CSPs, Proceedings of SODA'22. doi:10.1137/1.9781611977073.46
Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Živný, The complexity of approximately counting retractions to square-free graphs, ACM TALG 17(3), Article No. 22, 2021. doi:10.1145/3458040
Caterina Viola and Stanislav Živný, The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains, ACM TALG 17(3), Article No 21, 2021. doi:10.1145/3458041
Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný, Counting homomorphisms to K₄-minor-free graphs, modulo 2, SIDMA 35(4), pp. 2749–2814, 2021. doi:10.1137/20M1382921
Ragnar Groot Koerkamp and Stanislav Živný, On rainbow-free colourings of uniform hypergraphs , TCS 885(11), pp. 69–76, 2021. doi:10.1016/j.tcs.2021.06.022
Alex Brandts, Marcin Wrochna, and Stanislav Živný, The complexity of promise SAT on non-Boolean domains, ACM ToCT 13(4), Article No. 26, 2021. doi:10.1145/3470867
Eden Pelleg and Stanislav Živný, Additive sparsification of CSPs, Proceedings of ESA'21. doi:10.4230/LIPIcs.ESA.2021.75
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. doi:10.4230/LIPIcs.ESA.2021.58
Balázs Mezei, Marcin Wrochna, and Stanislav Živný, PTAS for sparse general-valued CSPs, Proceedings of LICS'21. doi:10.1109/LICS52264.2021.9470599
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₄-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, pp. 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), pp. 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), pp. 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), pp. 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, pp. 11–39, 2017. doi:10.1016/j.tcs.2017.05.001
Peter Fulla and Stanislav Živný, On planar valued CSPs, JCSS 87, pp. 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