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:

PhD students:
  • Diego Battistelli since 1 Oct 2018
  • 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: I have a postdoc position available, starting around Sep 2020 (see ad below)

Papers

  1. D. Zhuk, B. Martin, QCSP monsters and the demise of the Chen Conjecture, submitted [arXiv]
  2. L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, submitted [arXiv]
  3. L. Barto, M. Pinsker, Topology is irrelevant (in the infinite domain dichotomy conjecture for constraint satisfaction problems), submitted [arXiv]

  4. L. Barto, Accessible set endofunctors are universal, accepted to CMUC [arXiv]

  5. A. Mottet, K. Quaas, The containment problem for Unambiguous Register Automata, STACS'19 [arXiv] [DOI]
  6. 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]
  7. L. Barto, Promises make finite (constraint satisfaction) problems infinitary, LICS 2019 [arXiv] [DOI]
  8. L. Barto, Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps, FCT'19, 3-17. (invited talk, non-refereed) [arXiv] [DOI]

Conferences

  1. Sep 16-20 2019, L. Barto, invited talk Promise Constraint Satisfaction Problem at TbiLLC 2019, Tsikhisdziri, Georgia. [Slides]
  2. 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]
  3. Aug 11-14 2019, L. Barto, invited talk Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps at FCT, Copenhagen, Denmark. [Slides]
  4. Jun 25-28 2019: D. Battistelli Second Algebra Week, Siena, Italy.
  5. 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]
  6. 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]
  7. Jun 17-21 2019, L. Barto, tutorial Constraint Satisfaction Problems at Caleidoscope : Complexity as a Kaleidoscope, Paris, France. [Slides, part I] [Slides, part II]
  8. 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]
  9. May 10 2019: L. Barto, invited talk Algebraic theory of promise constraint satisfaction problems at Prague Gathering of Logicians 2019, Prague, Czechia. [Slides]
  10. 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
  11. Mar 13-16 2019: A. Mottet, talk The containment problem for unambiguous register automata at STACS 2019, Berlin, Germany. [Slides]
  12. 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]
  13. Oct 17-23 23 2018: A. Mottet, invitational workshop Unifying themes in Ramsey theory, Banff, Canada
  14. Sep 2-7 2018: L. Barto, member of the organizing quadrumvirate, [56th Summer School on Algebra and Ordered Sets], Spindleruv Mlyn, Czechia.
  15. 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]
  16. Jun 1-3 2018: L. Barto, invited talk Height one identities at 96. Arbeitstagung Allgemeine Algebra, Darmstadt, Germany. [Slides]

Visitors

  1. Jul 7-12 2019: Andrei Krokhin and Jakub Opršal
  2. Mar 3-7 2019: Jakub Opršal
  3. Mar 3-8 2019: Andrei Krokhin
  4. Jan 28 - Feb 1 2019: Marcin Kozik
  5. Dec 17-22 2018: Marcin Kozik
  6. Oct 15-26 2018: Marcin Kozik
  7. Mar 26- Apr 6 2018: Andrei Krokhin

Visits

  1. Jun 17-21 2019: A. Mottet meeting J. Opršal and B. Martin at TU Dresden
  2. May 6-11 2018: L. Barto visiting Andrei Krokhin at Durham University
  3. 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.

Call for applications: postdocs

We are looking for a highly motivated and creative post-doctoral researcher to work on the ERC funded project Symmetry in Computational Complexity (CoCoSym) under the supervision of Libor Barto at the Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague.

The project concerns the complexity and approximability of fixed-template constraint satisfaction problems over finite domains and their generalization to infinite domains and weighted relations.

The duration of the position will be between one and three years. The starting day is flexible, applications will be considered until the position is filled. The position carries no teaching load. The position is fully funded from the ERC grant, funding for conference travel is also available.

Applicants should send a CV, a statement of research experience and interests, and a list of publications (that may include a short annotation of at most three of their best papers) in a single PDF file to Libor Barto (libor.barto@mff.cuni.cz). Applicants should also arrange for at least two recommendation letters to be sent directly to the same email address. Informal inquiries are welcome.