Libor Barto

HOME COCOSYM RESEARCH FOR STUDENTS

Symmetry in Computational Complexity (CoCoSym)

Project funded by the European Research Council (ERC) as an ERC Consolidator Grant (ERC CoG), No. 771005

Principal investigator: Libor Barto
Postdocs:

  • Bertalan Bodor, 1 Nov 2021 - 31 Jan 2023
  • Michael Kompatscher, 1 Oct 2021 - 31 Jan 2023
  • Caterina Viola, 1 Jul 2022 - 31 Jan 2023
  • Dmitriy Zhuk, 1 Oct 2018 - 4 Mar 2019, 1 Dec 2021 - 31 Jan 2023
  • Kevin Berg, 15 Oct 2019 - 30 Jun 2022
  • William DeMeo, 15 Nov 2019 - 31 Jul 2021
  • Andrew Moorhead, 1 Sep 2019 - 8 Jan 2020
  • Antoine Mottet, 1 Sep 2018 - 28 Feb 2022
PhD students:
  • Kristina Asimi since 1 Dec 2018 - 31 Jan 2023
  • Diego Battistelli, 1 Oct 2018 - 23 Jan 2020

Host institution: Charles University, Prague, Czech Republic.
Department: Department of Algebra, Faculty of Mathematics and Physics
Dates: 1 Feb 2018 - 31 Jan 2023

Papers

  1. K. Asimi, L. Barto, V. Dalmau: The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side [arXiv]
  2. L. Barto, S. Butti, V. Dalmau: The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems [arXiv]
  3. J. Hubička, M. Kompatscher, M. Konečný, Forbidden cycles in metrically homogeneous graphs [arXiv]
  4. A. Aranda, D. Bradley-Williams, J. Hubička, M. Karamanlis, M. Kompatscher, M. Konečný, M. Pawliuk, Ramsey expansions of metrically homogeneous graphs [arXiv]

  5. L. Barto, A. Mottet: Finite Algebras with Hom-Sets of Polynomial Size, Transactions AMS 378 (2025), 569-596 [DOI] [arXiv]
  6. L. Barto, S. Butti, A. Kazda, C. Viola, S. Zivny, Algebraic Approach to Approximation, LICS 2024, 1-14 [arXiv] [DOI]
  7. L. Barto, Z. Brady, A. Bulatov, M. Kozik, D. Zhuk, Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras, TheoretiCS 3 (2024), 1-76 [DOI] [arXiv]
  8. L. Barto, B. Bodor, M. Kozik, A. Mottet, M. Pinsker, Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing, LICS 2023, 1-13 [arXiv] [DOI]
  9. D. Zhuk, B. Martin, M. Wrona, The complete classification for quantified equality constraints, SODA 2023, 2746-2760 [arXiv] [DOI]
  10. D. Zhuk, B. Martin, QCSP monsters and the demise of the Chen Conjecture, Journal of the ACM, 69/5 (2022), 1-44 [arXiv] [DOI]
  11. A. Moorhead, Higher Kiss terms, International Journal of Algebra and Computation, 32/06 (2022), 1233-1259 [arXiv] [DOI]
  12. A. Mottet, M. Pinsker, Smooth Approximations and CSPs over finitely bounded homogeneous structures, LICS 2022, 36:1-13 [arXiv] [DOI]
  13. L. Barto, S. Butti, Weisfeiler-Leman Invariant Promise Valued CSPs, CP 2022, 4:1-4:17 [arXiv] [DOI]
  14. K. Asimi, L. Barto, S. Butti, Fixed-Template Promise Model Checking Problems, CP 2022, 2:1-2:17 [arXiv] [DOI]
  15. L. Barto, M. Kozik, Combinatorial Gap Theorem and Reductions between Promise CSPs, SODA 2022, 1204-1220 [arXiv] [DOI]
  16. P. Gillibert, J. Jonušas, M. Kompatscher, A. Mottet, M. Pinsker, When Symmetries are not Enough: a Hierarchy of Hard Constraint Satisfaction Problems, SIAM Journal on Computing, 51/2 (2022), 175-213 [arXiv] [DOI]
  17. M. Bodirsky, F. Madelaine, A. Mottet, A proof of the algebraic tractability conjecture for Monotone Monadic SNP, SIAM Journal on Computing, 50/4 (2021), 1359-1409 [arXiv] [DOI]
  18. W. Czerwiński, A. Mottet, K. Quaas, New Techniques for Universality in Unambiguous Register Automata, ICALP 2021 [arXiv] [DOI]
  19. A. Mottet, T. Nagy, M. Pinsker, M. Wrona, Smooth Approximations and Relational Width Collapses, ICALP 2021, [arXiv] [DOI]
  20. A. Mottet, K. Quaas, The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata, Theory of Computing Systems 65 (2021), 706-735 [DOI]
  21. A. Mottet, M. Pinsker, Cores over Ramsey structures, Journal of Symbolic Logic 86/1 (2021), 352-361 [arXiv] [DOI]
  22. L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, Journal of the ACM 68/4 (2021), 1-66 [arXiv] [DOI]
  23. K. Asimi, L. Barto, Finitely Tractable Promise Constraint Satisfaction Problems, MFCS 2021 [DOI]
  24. L. Barto and W. DeMeo, A. Mottet, Constraint Satisfaction Problems over Finite Structures, LICS 2021 [arXiv] [DOI]
  25. L. Barto, Z. Brady, A. Bulatov, M. Kozik, D. Zhuk, Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP, LICS 2021 [arXiv] [DOI]
  26. L. Barto, D. Battistelli, K. M. Berg, Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case, STACS 2021 [DOI]
  27. M. Bodirsky, A. Mottet, M. Olsak, J. Oprsal, M. Pinsker, R. Willard, omega-categorical structures avoiding heigh 1 identities, Transactions of the AMS, 374 (2021), 327-350 [arXiv] [DOI]
  28. D. Zhuk, A Proof of the CSP Dichotomy Conjecture, Journal of the ACM, 67/5 (2020), 30:1-30:78 [arXiv] [DOI] [Presburger Award 2020]
  29. D. Zhuk, B. Martin, QCSP monsters and the demise of the Chen Conjecture, STOC 2020 [arXiv] [DRO] [DOI]
  30. P. Gillibert, J. Jonušas, M. Kompatscher, A. Mottet, M. Pinsker, Hrushovski’s Encoding and ω-Categorical CSP Monsters, ICALP 2020 [arXiv] [DOI]
  31. L. Barto, M. Kozik, J. Tan, M. Valeriote, Sensitive instances of the Constraint Satisfaction Problem, ICALP 2020 [arXiv] [DOI]
  32. L. Barto, M. Pinsker, Topology is irrelevant (in the infinite domain dichotomy conjecture for constraint satisfaction problems), SIAM Journal on Computing, 49/2 (2020), 365-393 [arXiv] [DOI]
  33. L. Barto, Accessible set endofunctors are universal, Commentationes Mathematicae Universitatis Carolinae 60/4 (2019), 497-508 [arXiv]
  34. A. Mottet, K. Quaas, The containment problem for Unambiguous Register Automata, STACS'19 [arXiv] [DOI]
  35. M. Bodirsky, A. Mottet, M. Olšák, J. Opršal, M. Pinsker, R. Willard, Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems), LICS 2019 [arXiv] [DOI]
  36. L. Barto, Promises make finite (constraint satisfaction) problems infinitary, LICS 2019 [arXiv] [DOI]
  37. L. Barto, Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps, FCT'19, 3-17. (invited talk, non-refereed) [arXiv] [DOI]

  38. L. Barto, Symetrie ve výpočetní složitosti, Vesmír, 101,559, 2022/9 (in Czech), popularizing article. [link]

Conferences, workshops, seminars

  1. Jan 2-5 2023, D. Zhuk, talk The Complete Classification for Quantified Equality Constraints SODA 2023, Florence, Italy. [Slides]
  2. Sep 26-30 2022, K. Asimi, D. Zhuk, LAP 2022, Dubrovnik, Croatia.
    • K. Asimi: Fixed-template Promise Model Checking Problems [Slides]
    • D. Zhuk: On the complexity of the Quantified Constraint Satisfaction Problem [Slides]
  3. Sep 18-24 2022, L. Barto, B. Bodor, M. Kompatscher, C. Viola, D. Zhuk, CWC 2022, Molveno, Italy.
  4. Jul 31 - Aug 5 2022, K. Asimi, talk Fixed-Template Promise Model Checking Problems at CP 2022, Haifa, Israel. [Slides]
  5. Jul 31 2022, K. Asimi, Women in Logic workshop (WiL 2022), Haifa, Israel. (Joint work with L.B. and Silvia Butti presented by Silvia.)
  6. Jul 13 2022, D. Zhuk, invited talk Constraint Satisfaction Problem: what makes the problem easy at ICM [Slides] [Video]
  7. Jul 4 2022, L. Barto, invited talk CSPs and Set Functors at Structure Meets Power, affiliated workshop to ICALP, Paris. [Slides]
  8. Jun 30 2022, L. Barto, invited tutorial Algebra and Logic in the Complexity of Constraints at Logic Colloquium 2022, Reykjavik, Iceland. [Slides]
  9. Jun 24-26 2022, B. Bodor, M. Kompatscher, D. Zhuk, AAA102, Szeged, Hungary.
  10. May 15-20 2022, K. Asimi, L. Barto, B. Bodor, M. Kompatscher, D. Zhuk, Dagstuhl workshop (invitational) The Constraint Satisfaction Problem: Complexity and Approximability
    • L. Barto: Combinatorial value and gap amplification [Slides]
    • M. Kompatscher: Finitely tractable PCSPs [Slides]
    • D. Zhuk: PSpace-hard vs Π^P_2 Dichotomy of the QCSP [Slides]
  11. Mar 11 2022, B. Bodor, talk Structures with at most (2−ε)-exponential unlabelled growth at ECIMT
  12. Feb 10 2022, L. Barto, talk The number of homomorphisms into finite algebras at TCS lab seminar, HSE University, Russia (online). [Slides]
  13. Sep 26- Oct 2 2021, K. Asimi, L. Barto, K. Berg, A. Mottet, CSP World Congress 2021, Kranjska Gora, Slovenia.
  14. Aug 26 2021, K. Asimi, talk Finitely Tractable Promise Constraint Satisfaction Problems at MFCS, Tallinn, Estonia.
  15. Jun 29 2021, L. Barto, A. Mottet, LICS, online.
  16. Jun 6, 2021, K. Berg, talk Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case at AAA 101 (online).
  17. May 27 2021, L. Barto, invited talk Minimal Taylor Clones at ISMVL, Nursultan, Kazahstan (online). [Slides]
  18. May 24 2021, L. Barto, talk CSPs and Symmetries at Symmetry in New Castle seminar, The University of Newcastle, Australia (online).
  19. Mar 17 2021, K. Berg, talk Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case at STACS, Saarbrucken, Germany (online). [Slides (for video)] [Slides (short)] [Video]
  20. Feb 23 2021, K. Asimi, talk Finitely tractable PCSPs at PALS seminar, CU Boulder, USA (online). [Video]
  21. Feb 11 2021, L. Barto, talk Finitely tractable PCSPs at Ulam Seminar, CU Boulder, USA (online). [Slides] [Video]
  22. Feb 5-7 2021, L. Barto, invited talk Algebras with polynomially many homomorphisms at AAA 100, Krakow, Poland (online). [Slides]
  23. Jan 4,5 2021, L. Barto, A. Mottet, Homogeneous structures: model theory meets universal algebra, Oberwolfach, Germany (online).
    • L. Barto: 2 tutorial lectures Universal Algebra: Tutorial [Slides]
    • A. Mottet: Smooth Approximations [Slides] [Video]
  24. Oct 7, 2020, W. DeMeo, talk Complexity of the Homomorphism Problem for Boolean Models, Online CSP seminar. [Slides] [Video]
  25. Oct 7 2020, L. Barto, talk CSPs and Symmetries, 19th Jarnik lecture, Prague, Czechia. [Slides]
  26. Sep 20-26 2020, K. Asimi, L. Barto, K. Berg, A. Mottet, W. DeMeo CSP World Congress 2020, Voels am Schlern, Italy.
  27. Aug 6 2020, A. Mottet, talk Cores over Ramsey structures at Midsummer Combinatorial Workshop XXIV, Prague, Czechia.
  28. Jul 23 2020, L. Barto, talk Baby PCP Theorem and reductions between Promise CSPs at Online CSP seminar. [Slides] [Video]
  29. Jul 8-11 2020, L. Barto, talk Sensitive instances of the Constraint Satisfaction Problem at ICALP 2020, online. [Slides] [Video]
  30. Feb 21-23 2020, K. Asimi, L. Barto, K. Berg AAA99, Siena, Italy.
    • K. Asimi: Infinity: Relevant or Irrelevant? [Slides]
    • L. Barto: Reconstructing subproducts from projections [Slides]
    • K. Berg: The Complexity of Homomorphism Factorization [Slides]
  31. Jan 27-31 2020, L. Barto, invited talk Promise Constraint Satisfaction at ATCAGC 2020: Algebraic, Topological and Complexity Aspects of Graph Covers , Bedrichov, Czechia. [Slides]
  32. Jan 12-17, A. Mottet, Ackermann Award 2019 invited talk Dichotomies in constraint satisfaction: canonical functions and numeric CSPs at CSL 2020, Barcelona, Spain. [Slides]
  33. Oct 3-5 2019, K. Asimi, talk Promises turn finite problems to infinite ones at Congress of Young Mathematicians, Novi Sad, Serbia. [Slides (Serbian)]
  34. Sep 16-20 2019, L. Barto, invited talk Promise Constraint Satisfaction Problem at TbiLLC 2019, Tsikhisdziri, Georgia. [Slides]
  35. Sep 1-7 2019, K. Asimi, L. Barto, D. Battistelli, A. Mottet 57th Summer School on Algebra and Ordered Sets, Karolinka, Czechia.
    • K. Asimi: Infinite nature of finite PCSPs [Slides]
    • L. Barto: A hardness criterion for Promise CSPs [Slides]
    • D. Battistelli: On the complexity of symmetric Promise CSP [Slides]
    • A. Mottet: Topology is relevant in infinite-domain constraint satisfaction [Slides]
  36. Aug 11-14 2019, L. Barto, invited talk Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps at FCT, Copenhagen, Denmark. [Slides]
  37. Jun 25-28 2019: D. Battistelli Second Algebra Week, Siena, Italy.
  38. Jun 24-27 2019: L. Barto, A. Mottet LICS 2019, Vancouver, Canada.
    • L. Barto: Promises Make Finite (Constraint Satisfaction) Problems Infinitary [Slides]
    • A. Mottet: Topology is relevant (in a dichotomy conjecture for infinite-domain CSPs) [Slides]
  39. Jun 21-23 2019: K. Asimi, D. Battistelli, D. Zhuk AAA98, Dresden, Germany.
    • D. Zhuk, The complexity of the Quantified Constraint Satisfaction Problem on a 3-element set [Slides]
  40. Jun 17-21 2019, L. Barto, tutorial Constraint Satisfaction Problems at Caleidoscope : Complexity as a Kaleidoscope, Paris, France. [Slides, part I] [Slides, part II]
  41. Jun 9-11 2019: K. Asimi, A. Mottet, D. Zhuk Russian Workshop on Complexity and Model Theory, Moscow, Russia.
    • D. Zhuk, The complexity of the Quantified Constraint Satisfaction Problem on a 3-element set [Slides]
  42. May 10 2019: L. Barto, invited talk Algebraic theory of promise constraint satisfaction problems at Prague Gathering of Logicians 2019, Prague, Czechia. [Slides]
  43. Apr 4-7 2019: K. Asimi, D. Battistelli, A. Mottet, Spring School of the Department of Algebra, Sec-Ustupky, Czechia.
    • K. Asimi, Infinity is Relevant
    • D. Battistelli, Ultrafilters and Compactness of Topological Spaces
  44. Mar 13-16 2019: A. Mottet, talk The containment problem for unambiguous register automata at STACS 2019, Berlin, Germany. [Slides]
  45. Mar 1-3 2019: K. Asimi, L. Barto, D. Battistelli, A. Mottet, D. Zhuk AAA97, Vienna, Austria.
    • L. Barto, A loop lemma for nonidempotent cores [Slides]
    • A. Mottet, Topology is relevant [Slides]
    • D. Zhuk, An exponential lower bound on the size of primitive positive definition [Slides]
  46. Oct 17-23 2018: A. Mottet, invitational workshop Unifying themes in Ramsey theory, Banff, Canada
  47. Sep 2-7 2018: L. Barto, member of the organizing quadrumvirate, [56th Summer School on Algebra and Ordered Sets], Spindleruv Mlyn, Czechia.
  48. Jun 4-8 2018: L. Barto, talk at invitational workshop Cyclic operations in promise constraint satisfaction problems at Dagstuhl workshop The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany. [Slides]
  49. Jun 1-3 2018: L. Barto, invited talk Height one identities at 96. Arbeitstagung Allgemeine Algebra, Darmstadt, Germany. [Slides]

Visitors

  1. Jun 20-Sep 29 2021: Silvia Butti
  2. Aug 25-Sep 8 2020: Jakub Opršal (co-funded by GAČR 18-20123S)
  3. Feb 17-20 2020: Marcin Kozik
  4. Dec 9-13 2019: Marcin Kozik
  5. Nov 17-26 2019: Dmitriy Zhuk
  6. Oct 23-29 2019 Ralph McKenzie
  7. Jul 7-12 2019: Andrei Krokhin and Jakub Opršal
  8. Mar 3-7 2019: Jakub Opršal
  9. Mar 3-8 2019: Andrei Krokhin
  10. Jan 28 - Feb 1 2019: Marcin Kozik
  11. Dec 17-22 2018: Marcin Kozik
  12. Oct 15-26 2018: Marcin Kozik
  13. Mar 26- Apr 6 2018: Andrei Krokhin

Visits

  1. Jun 26 - July 25 2022, K. Asimi visiting Victor Dalmau at University Pompeu Fabra
  2. Dec 12-17 2019: A. Mottet visiting Michael Pinsker at TU Wien (seminar talk "Cores of structures of Ramsey expansion")
  3. Nov 10-17 2019: A. Moorhead visiting Erhard Aichinger and his group at JKU Linz (seminar talks, including "What is the right definition of supernilpotence")
  4. Oct 20-26 2019: A. Mottet visiting J. Thapper, P. Koiran, and others at University Paris-Est, University Paris 7, ENS Lyon (seminar talk "Symmetries in infinite-domain constraint satisfaction." at each of the universities)
  5. Oct 6-7 2019: L. Barto visiting Michal Botur at Palacky University (seminar talk "Mathematics in coloring problems with promises")
  6. Jun 17-21 2019: A. Mottet meeting Jakub Opršal and Barnaby Martin at TU Dresden
  7. Feb 10-16 2019: L. Barto visiting Marcin Kozik and Miroslav Olsak at Jagiellonian University
  8. May 6-11 2018: L. Barto visiting Andrei Krokhin at Durham University
  9. Feb 23 - Mar 5 2018: L. Barto visiting Marcin Kozik at Jagiellonian University

Abstract

The last 20 years of rapid development in the computational-theoretic aspects of the fixed-language Constraint Satisfaction Problems (CSPs) has been fueled by a connection between the complexity and a certain concept capturing symmetry of computational problems in this class.

My vision is that this connection will eventually evolve into the organizing principle of computational complexity and will lead to solutions of fundamental problems such as the Unique Games Conjecture or even the P-versus-NP problem. In order to break through the current limits of this algebraic approach, I will concentrate on specific goals designed to

  1. discover suitable objects capturing symmetry that reflect the complexity in problem classes, where such an object is not known yet;
  2. make the natural ordering of symmetries coarser so that it reflects the complexity more faithfully;
  3. delineate the borderline between computationally hard and easy problems;
  4. strengthen characterizations of existing borderlines to increase their usefulness as tools for proving hardness and designing efficient algorithm; and
  5. design efficient algorithms based on direct and indirect uses of symmetries.
The specific goals concern the fixed-language CSP over finite relational structures and its generalizations to infinite domains (∞CSP) and weighted relations (vCSP), in which the algebraic theory is highly developed and the limitations are clearly visible.

The approach is based on joining the forces of the universal algebraic methods in finite domains, model-theoretical and topological methods in the ∞CSP, and analytical and probabilistic methods in the vCSP. The starting point is to generalize and improve the Absorption Theory from finite domains.