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:
PhD students:
 Diego Battistelli, 1 Oct 2018  23 Jan 2020
 Kristina Asimi since 1 Dec 2018
Host institution: Charles University, Prague, Czech Republic.
Department: Department of Algebra, Faculty of Mathematics and Physics
Dates: 1 Feb 2018  31 Jan 2023
Openings: contact me
Papers
 A. Mottet, Smooth Approximations and CSPs over finitely bounded homogeneous structures, submitted
[arXiv]
 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, submitted
[old preprint]
 L. Barto and W. DeMeo, A. Mottet, Constraint Satisfaction Problems over Finite Structures, submitted
[arXiv]
 K. Asimi, L. Barto, Finitely Tractable Promise Constraint Satisfaction Problems, in preparation
[arXiv]
 A. Moorhead, Higher Kiss terms, submitted
[arXiv]
 L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, submitted
[arXiv]
 L. Barto, D. Battistelli, K. M. Berg, Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean
Case, to appear at STACS 2021
[arXiv]
 A. Mottet, M. Pinsker, Cores over Ramsey structures, Journal of Symbolic Logic (online)
[arXiv]
[DOI]
 A. Mottet, K. Quaas, The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata,
Theory of Computing Systems (2020)
[DOI]
 M. Bodirsky, A. Mottet, M. Olsak, J. Oprsal, M. Pinsker, R. Willard, omegacategorical structures avoiding heigh 1 identities,
Transactions of the AMS, 374 (2021), 327350
[arXiv]
[DOI]
 D. Zhuk, A Proof of the CSP Dichotomy Conjecture, Journal of the ACM, 67/5 (2020), 30:130:78
[arXiv]
[DOI]
[Presburger Award 2020]
 D. Zhuk, B. Martin, QCSP monsters and the demise of the Chen Conjecture, STOC 2020
[arXiv]
[DRO]
[DOI]
 P. Gillibert, J. Jonušas, M. Kompatscher, A. Mottet, M. Pinsker, Hrushovski’s Encoding and ωCategorical CSP Monsters, ICALP 2020
[arXiv]
[DOI]
 L. Barto, M. Kozik, J. Tan, M. Valeriote,
Sensitive instances of the Constraint Satisfaction Problem, ICALP 2020
[arXiv]
[DOI]
 L. Barto, M. Pinsker, Topology is irrelevant (in the infinite domain dichotomy conjecture for constraint satisfaction problems),
SIAM Journal on Computing, 49/2 (2020), 365393
[arXiv]
[DOI]
 L. Barto, Accessible set endofunctors are universal, Commentationes Mathematicae Universitatis Carolinae 60/4 (2019), 497508
[arXiv]
 A. Mottet, K. Quaas, The containment problem for Unambiguous Register Automata,
STACS'19
[arXiv]
[DOI]
 M. Bodirsky, A. Mottet, M. Olšák, J. Opršal, M. Pinsker, R. Willard, Topology is relevant (in a dichotomy conjecture for infinitedomain constraint satisfaction problems), LICS 2019
[arXiv] [DOI]
 L. Barto, Promises make finite (constraint satisfaction) problems infinitary, LICS 2019
[arXiv] [DOI]
 L. Barto, Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps,
FCT'19, 317. (invited talk, nonrefereed)
[arXiv] [DOI]
Conferences, workshops, seminars
 Feb 11 2021, L. Barto, talk Finitely tractable PCSPs at
Ulam Seminar, CU Boulder, USA.
[Slides]
[Video]
 Feb 57 2021, L. Barto, invited talk Algebras with polynomially many homomorphisms at AAA 100, Krakow, Poland (online).
[Slides]
 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]
 Oct 7 2020, L. Barto, talk CSPs and Symmetries,
19th Jarnik lecture, Prague, Czechia.
[Slides]
 Sep 2026 2020, K. Asimi, L. Barto, K. Berg, A. Mottet, W. DeMeo CSP World Congress 2020,
Voels am Schlern, Italy.
 Aug 6 2020, A. Mottet, talk Cores over Ramsey structures at
Midsummer Combinatorial Workshop XXIV, Prague, Czechia.
 Jul 23 2020, L. Barto, talk Baby PCP Theorem and reductions between Promise CSPs at
Online CSP seminar.
[Slides]
[Video]
 Jul 811 2020, L. Barto, talk Sensitive instances of the Constraint Satisfaction Problem at
ICALP 2020, online.
[Slides]
[Video]
 Feb 2123 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]
 Jan 2731 2020, L. Barto, invited talk Promise Constraint Satisfaction at ATCAGC 2020: Algebraic, Topological and Complexity Aspects of Graph Covers , Bedrichov, Czechia.
[Slides]
 Jan 1217, A. Mottet, Ackermann Award 2019 invited talk Dichotomies in constraint satisfaction: canonical functions and numeric CSPs at CSL 2020, Barcelona, Spain.
[Slides]
 Oct 35 2019, K. Asimi, talk Promises turn finite problems to infinite ones at
Congress of Young Mathematicians, Novi Sad, Serbia.
[Slides (Serbian)]
 Sep 1620 2019, L. Barto, invited talk Promise Constraint Satisfaction Problem at TbiLLC 2019, Tsikhisdziri, Georgia.
[Slides]
 Sep 17 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 infinitedomain constraint satisfaction [Slides]
 Aug 1114 2019, L. Barto, invited talk Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps at FCT, Copenhagen, Denmark.
[Slides]
 Jun 2528 2019: D. Battistelli Second Algebra Week, Siena, Italy.
 Jun 2427 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 infinitedomain CSPs) [Slides]
 Jun 2123 2019: K. Asimi, D. Battistelli, D. Zhuk AAA98, Dresden, Germany.
 D. Zhuk, The complexity of the Quantified Constraint Satisfaction Problem on a 3element set
[Slides]
 Jun 1721 2019, L. Barto, tutorial Constraint Satisfaction Problems at Caleidoscope : Complexity as a Kaleidoscope, Paris, France.
[Slides, part I]
[Slides, part II]
 Jun 911 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 3element set
[Slides]
 May 10 2019: L. Barto, invited talk Algebraic theory of promise constraint satisfaction problems at Prague Gathering of Logicians 2019, Prague, Czechia.
[Slides]
 Apr 47 2019: K. Asimi, D. Battistelli, A. Mottet, Spring School of the Department of Algebra, SecUstupky, Czechia.
 K. Asimi, Infinity is Relevant
 D. Battistelli, Ultrafilters and Compactness of Topological Spaces
 Mar 1316 2019: A. Mottet, talk The containment problem for
unambiguous register automata at STACS 2019, Berlin, Germany.
[Slides]
 Mar 13 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]

Oct 1723 2018: A. Mottet, invitational workshop
Unifying themes in Ramsey theory, Banff, Canada

Sep 27 2018: L. Barto, member of the organizing quadrumvirate,
[56th Summer School on Algebra and Ordered Sets], Spindleruv Mlyn, Czechia.

Jun 48 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]

Jun 13 2018: L. Barto, invited talk Height one identities at
96. Arbeitstagung Allgemeine Algebra, Darmstadt, Germany.
[Slides]
Visitors
 Aug 25Sep 8 2020: Jakub Opršal (cofunded by GAČR 1820123S)
 Feb 1720 2020: Marcin Kozik
 Dec 913 2019: Marcin Kozik
 Nov 1726 2019: Dmitriy Zhuk
 Oct 2329 2019 Ralph McKenzie
 Jul 712 2019: Andrei Krokhin and Jakub Opršal
 Mar 37 2019: Jakub Opršal
 Mar 38 2019: Andrei Krokhin
 Jan 28  Feb 1 2019: Marcin Kozik
 Dec 1722 2018: Marcin Kozik
 Oct 1526 2018: Marcin Kozik
 Mar 26 Apr 6 2018: Andrei Krokhin
Visits
 Dec 1217 2019: A. Mottet visiting Michael Pinsker at TU Wien (seminar talk "Cores of structures of Ramsey expansion")
 Nov 1017 2019: A. Moorhead visiting Erhard Aichinger and his group at JKU Linz (seminar talks, including "What is the right definition of supernilpotence")
 Oct 2026 2019: A. Mottet visiting J. Thapper, P. Koiran, and others at University ParisEst, University Paris 7, ENS Lyon (seminar talk "Symmetries in infinitedomain constraint satisfaction." at each of the universities)
 Oct 67 2019: L. Barto visiting Michal Botur at Palacky University (seminar talk "Mathematics in coloring problems with promises")
 Jun 1721 2019: A. Mottet meeting Jakub Opršal and Barnaby Martin at TU Dresden
 Feb 1016 2019: L. Barto visiting Marcin Kozik and Miroslav Olsak at Jagiellonian University
 May 611 2018: L. Barto visiting Andrei Krokhin at Durham University
 Feb 23  Mar 5 2018: L. Barto visiting Marcin Kozik at Jagiellonian University
Abstract
The last 20 years of rapid development in the computationaltheoretic aspects of the fixedlanguage
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 PversusNP problem. In order to break through the current limits of this algebraic
approach, I will concentrate on specific goals designed to
 discover suitable objects capturing symmetry that reflect the complexity in problem classes, where
such an object is not known yet;
 make the natural ordering of symmetries coarser so that it reflects the complexity more faithfully;
 delineate the borderline between computationally hard and easy problems;
 strengthen characterizations of existing borderlines to increase their usefulness as tools for proving
hardness and designing efficient algorithm; and
 design efficient algorithms based on direct and indirect uses of symmetries.
The specific goals concern the fixedlanguage 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,
modeltheoretical 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.
