Research interests: Universal algebra, computational complexity, in particular constraint satisfaction problems
IN PROGRESS
 L. Barto, M. Kozik, New Loop Lemmata, in preparation
 L. Barto, L. Ham, M. Jackson, Flexible CSPs, in preparation
BOOK CHAPTERS
 (survey) L. Barto, A. Krokhin, R. Willard, Polymorphisms, and how to use them,
in
"The Constraint Satisfaction Problem: Complexity and Approximability", Dagstuhl FollowUps, vol. 7, 1–44, 2017
[paper]
[complete volume].
 (survey) L. Barto, M. Kozik, Absorption in Universal Algebra and CSP,
in "The Constraint
Satisfaction Problem: Complexity and Approximability", Dagstuhl FollowUps, vol. 7, 45–77, 2017
[paper]
[complete volume].
JOURNAL PAPERS
 L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction,
Journal of the ACM 68/4 (2021), 166
[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]
 L. Barto, M. Kompatscher, M. Olsak, M. Pinsker, T. Van Pham, Equations in oligomorphic clones and the
constraint satisfaction problem for omegacategorical structures, Journal of Mathematical Logic 19/2 (2019), 1950010 (31 pages)
[arXiv]
[DOI]
 L. Barto, O. Draganov, The minimal arity of nearunanimity polymorphisms, Mathematica Slovaca 69/2 (2019), 297310
[arXiv]
[DOI]
 L. Barto, J. Oprsal, M. Pinsker, The wonderland of reflections,
Israel Journal of Mathematics 223/1 (2018), 363398
[preprint]
[DOI]
 L. Barto, Finitely related algebras in congruence modular varieties have few subpowers, Journal of the EMS 20/6 (2018), 14391471
[DOI]
[preprint]
 L. Barto, J. Bulin, Deciding absorption in relational structures, Algebra Universalis 78/1 (2017), 318
[DOI]
[arXiv]
 L. Barto, The collapse of the bounded width hierarchy, Journal of Logic and Computation 26/3 (2016), 923943
[DOI]
[preprint]
 L. Barto, A. Kazda, Deciding absorption, Int. J. Algebra Comput. 26/05 (2016), 10331060
[DOI]
[arXiv]
 L. Barto, M. Kozik, Robustly solvable constraint satisfaction problems, SIAM Journal on Computing 454 (2016), 16461669
[DOI]
[arXiv]
 (survey) L. Barto, The constraint satisfaction problem and universal algebra, The Bulletin of Symbolic Logic 21/03 (2015), 319337.
[DOI]
[preprint]
 L. Barto, M. Kozik, D. Stanovsky, Mal'tsev conditions, lack of absorption, and solvability, Algebra Universalis 74/12 (2015), 185206
[DOI]
[preprint]
 L. Barto, M. Kozik, Constraint satisfaction problems solvable by local consistency methods, Journal of the ACM 61/1 (2014), 3:13:19
[DOI]
 L. Barto, J. Bulin, CSP dichotomy for special polyads, Int. J. Algebra Comput. 23/05 (2013), 11511174
[DOI]
[preprint]
 L. Barto, Finitely related algebras in congruence distributive varieties have near unanimity terms, Canadian Journal of Mathematics 65/1 (2013), 321
[DOI]
[preprint]
 L. Barto, M. Kozik, Absorbing subalgebras, cyclic terms and the constraint satisfaction problem,
Logical Methods in Computer Science 8/1:07 (2012), 126.
[preprint]
 L. Barto, D. Stanovsky, Polymorphisms of small digraphs,
Novi Sad J. Math. 40/2 (2010), 95109
[ paper & data ]
 L. Barto, M. Kozik, Cyclic terms for SD(v) varieties  revisited, Algebra Universalis 64/12 (2010), 137142
[ DOI ],
[preprint]
 L. Barto, M. Kozik, Congruence distributivity implies bounded width, SIAM Journal on Computing 39/4 (2009), 15311542
[preprint]
 L. Barto, M. Kozik, M. Maroti, R. McKenzie, T. Niven,
Congruence modularity implies cyclic terms for finite algebras, Algebra Universalis 61/3 (2009), 365380
[preprint]
 L. Barto, M. Kozik, M. Maroti, T. Niven,
CSP dichotomy for special triads, Proc. Amer. Math. Soc. 137/9 (2009), 29212934.
[preprint]
[errata!]
 L. Barto, Slices of essentially algebraic categories,
Applied Categorical Structures 17/2 (2009), 119152.
[preprint]
 L. Barto, M. Kozik, T. Niven,
The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of BangJensen and Hell),
SIAM Journal on Computing 38/5 (2009), 17821802.
[preprint]
 L. Barto, The category of varieties and interpretations is alguniversal,
Journal of Pure and Applied Algebra 211/3 (2007), 721731.
[preprint]
 L. Barto, Finitary set endofunctors are alguniversal,
Algebra Universalis 57/1 (2007), 1526.
[preprint]
 L. Barto, P. Zima, Every group is representable by all natural transformations of some setfunctor,
Theory and Applications of Categories 14/13 (2005), 294309.
[download]
 L. Barto, Weakly terminal objects in quasicategories of set endofunctors,
Applied Categorical Structures 13/3 (2005), 257264.
[preprint]
CONFERENCE PAPERS
 L. Barto, M. Kozik, Combinatorial Gap Theorem and Reductions between Promise CSPs, accepted to SODA 2022
[arXiv]
 K. Asimi, L. Barto, Finitely Tractable Promise Constraint Satisfaction Problems,
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021),
11:111:16
[DOI]
 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,
36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021),
113
[arXiv]
[DOI]
 L. Barto, W. DeMeo, A. Mottet, Constraint Satisfaction Problems over Finite Structures,
36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021),
1  13
[arXiv]
[DOI]
 L. Barto, D. Battistelli, K. M. Berg, Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean
Case,
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021),
10:110:16
[DOI]
 L. Barto, M. Kozik, J. Tan, M. Valeriote,
Sensitive instances of the Constraint Satisfaction Problem, in
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020),
110:1110:18
[arXiv]
[DOI]
 L. Barto, Promises make finite (constraint satisfaction) problems infinitary,
Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), LICS'19, 18
[arXiv]
[DOI]
 L. Barto, Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps,
FCT'19, 317. (invited talk, nonrefereed)
[arXiv] [DOI]
 L. Barto, M. Kompatscher, M. Olsak, T. Van Pham, M. Pinsker,
The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems,
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'17, 112.
[DOI]
[arXiv]
 L. Barto, M. Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems,
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'16, 615622.
[preprint]
 L. Barto, M. Kozik, R. Willard, Near unanimity constraints have bounded pathwidth duality,
Proceedings of the 27th ACM/IEEE Symposium on Logic in Computer Science, LICS'12, 125134.
[preprint].
 L. Barto, M. Kozik, Robust satisfiability of constraint satisfaction problems,
Proceedings of the 44th symposium on Theory of Computing, STOC'12 (2012), 931940.
[preprint]. Also published in ECCC, Report No. 163 (2011).
 L. Barto, The dichotomy for conservative constraint satisfaction problems revisited,
Proceedings of the 26th IEEE Symposium on Logic in Computer Science, LICS'11, 301310
[preprint]

L. Barto, M. Kozik, New conditions for Taylor varieties and CSP,
Proceedings of the 25th IEEE Symposium on Logic in Computer Science, LICS'10, 100109
[ DOI ]
 L. Barto, M. Kozik, Constraint satisfaction problems of bounded width,
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS'09 (2009), 595603
[preprint]
 L. Barto, M. Kozik, T. Niven,
Graphs, Polymorphisms and the Complexity of Homomorphism Problems,
Proceedings of the 40th ACM Symposium on Theory of Computing, STOC'08 (2008), 789796.
OTHER PAPERS
 (survey) L. Barto,
Constraint satisfaction problem and universal algebra,
ACM SIGLOG News 1/2 (2014), 1424.
[PDF] [The whole issue]
THESES
 L. Barto, Full embeddings and their modifications, PhD thesis, Charles University in Prague, 2006
[PDF] [PS]
 L. Barto, Funktory blízké úplným vnořením, Master's thesis, Charles University in Prague, 2003 (in Czech)
LECTURE NOTES
 D. Stanovsky, L. Barto, Pocitacova algebra (Computer algebra), Matfyzpress, 2011
MISC
FUTURE TALKS
 Jul 2020 Cancelled, TBA at Mathematics of Constraint Satisfaction, Durham, UK.
INVITED TALKS
 May 2021, Minimal Taylor Clones at ISMVL, Nursultan, Kazahstan (online).
[Slides]
 Feb 2021, Algebras with polynomially many homomorphisms at AAA 100, Krakow, Poland.
[Slides]
 Jan 2020, Promise Constraint Satisfaction at ATCAGC 2020: Algebraic, Topological and Complexity Aspects of Graph Covers , Bedrichov, Czechia.
[Slides]
 Sep 2019, Promise Constraint Satisfaction Problem at TbiLLC 2019: Thirteenth International Tbilisi Symposium on Language, Logic and Computation, Tsikhisdziri, Georgia.
[Slides]
 Aug 2019, Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps at FCT, Copenhagen, Denmark.
[Slides]
 May 2019, Algebraic theory of promise constraint satisfaction problems at Prague Gathering of Logicians 2019, Prague, Czechia.
[Slides]

June 2018  Height one identities at
96. Arbeitstagung Allgemeine Algebra, Darmstadt, Germany.
[Slides]
 August 2017  Equationally nontrivial algebras at
BLAST, Nashville, TN, USA.
[Slides]

November 2016  {Symmetry, Logic, CSP} at the workshop
{Symmetry, Logic, Computation},
part of the programme
Logical Structures in Computation,
Berkeley, USA.
[Slides]

August 2016  Infinite domain constraint satisfaction problem at
CSL, Marseille, France.
[Slides]

August 2016  The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
at special session "Homogeneous structures: model theory meets universal algebra" of Logic Colloquiuim, Leeds, UK.
[Slides]

May 2015  A rectangularity theorem for simple Taylor algebras at
Open Problems in Universal Algebra
,
a Shanks workshop at Vanderbilt University, Nashville, USA.

February 2015  Weighted clones at
89th Arbeitstagung Allgemeine Algebra, Dresden, Germany.
[Slides]

May 2014  Universal algebra and the constraint satisfaction problem at
Association of Symbolic Logic North American Annual Meeting, Boulder, CO, USA.
[Slides]

September 2013  Finitely related algebras at
The 51st Summer School on General Algebra and Ordered Sets, Trojanovice, Czech Republic.
[Slides]

July 2013  The distance from congruence distributivity to near unanimity at GAIA 2013: General Algebra and its Applications, Melbourne, Australia.
[Slides]

June 2013  Prime Maltsev conditions at 4th Novi Sad Algebraic Conference, Novi Sad, Serbia.
[Slides]

February 2013  Decision, counting and optimisation in constraint satisfaction problems at A Gathering of PragueBased Logicians,
Prague, Czech Republic.

June 2012  The Valeriote conjecture at Conference on Universal Algebra and Lattice Theory, Szeged, Hungary.
[Slides]

March 2012  Robust algorithms for CSPs at 83th Arbeitstagung Allgemeine Algebra, Novi Sad, Serbia.
[Slides]
 June 2011  Instances of the Constraint Satisfaction Problem in Universal Algebra at Second International Conference on Order, Algebra and Logics, Krakow, Poland.
[Slides]
 June 2010  An Application of CSP to Universal Algebra: A Proof of "The Crazy Z\'adori's Conjecture" at Workshop on Universal Algebra, Complexity and Constraint Satisfaction Problems, Lisbon, Portugal.
 August 2009  Prague Strategies at Novi Sad Algebraic Conference, Novi Sad, Serbia.
[Slides]
 November 2008  Constraint Satisfaction Problems of Bounded Width
at Eduard Cech Center meeting, Trest, Czech Republic
[Slides]
TUTORIALS
 Jan 2021, Universal Algebra: Tutorial at Homogeneous structures: model theory meets universal algebra, Oberwolfach, Germany.
[Slides]
 June 2019, Constraint satisfaction problems at Caleidoscope : Complexity as a Kaleidoscope, Institute Henri Poincare, Paris, France.
[Slides, part I]
[Slides, part II]
 September 2017  Universal algebra today at
55th Summer School on Algebra and Ordered Sets, Novy Smokovec, Slovakia.
[Slides I]
[Slides II]
[Slides III]

September 2015  Constraint satisfaction problem over a fixed template at
Highlights of Logic, Games and Automata
,
Prague, Czech Republic.
[Slides]
TALKS AT INVITATIONAL WORKSHOPS
 June 2018  Cyclic operations in promise constraint satisfaction problems at Dagstuhl workshop
The Constraint Satisfaction Problem: Complexity and Approximability,
Schloss Dagstuhl, Germany.
[Slides]

October 2015  The CSP basics revisited at Dagstuhl workshop
Duality in Computer Science
Schloss Dagstuhl, Germany.

July 2015  CSPs over hereditarily semisimple algebra at Dagstuhl workshop
The Constraint Satisfaction Problem: Complexity and Approximability
,
Schloss Dagstuhl, Germany.

November 2014  The basic CSP reductions revisited at BIRS Workshop
Algebraic and Model Theoretical Methods in Constraint Satisfaction, Banff, Canada.
[Slides]

November 2012  Robust Satisfiability of CSPs at the workshop The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany.
[Slides]
OTHER CONFERENCE TALKS
 September 2021, We can't compose at CSP World Congress 2021,
Kranjska Gora, Slovenia.
 September 2020, Noncollapse of width at CSP World Congress 2020,
Voels am Schlern, Italy.
 July 2020, Sensitive instances of the Constraint Satisfaction Problem at
ICALP, online.
[Slides]
[Video]
 February 2020, Reconstructing subproducts from projections at 99th Arbeitstagung Allgemeine Algebra, Siena, Italy.
[Slides]
 September 2019, A hardness criterion for Promise CSPs at 57th Summer School on Algebra and Ordered Sets, Karolinka, Czechia.
[Slides]
 June 2019, Promises make finite (constraint satisfaction) problems infinitary at
LICS, Vancouver, Canada.
[Slides]

March 2019  A loop lemma for nonidempotent cores at
97th Arbeitstagung Allgemeine Algebra,
Wien, Austria.
[Slides]

June 2017  Cores of oligomorphic clones revisited at
94th Arbeitstagung Allgemeine Algebra + 5th Novi Sad Algebraic Conference,
Novi Sad, Serbia.

September 2016  Local Loop Lemma at
The 54th Summer School on General Algebra and Ordered Sets, Trojanovice, Czech Republic.
[Slides]

September 2014  On simple Taylor algebras at 52nd Summer School on Algebra and Ordered Sets, Stara Lesna, Slovakia.
[Slides]

September 2012  Decidability of absorption for relational structures at 50th Summer School on Algebra and Ordered Sets, Novy Smokovec, Slovakia.
[Slides]
 August 2011  Robust approximation of CSPs at Workshop on Approximability of CSPs, Toronto, Canada.
 August 2011  A welcome conservative talk at Workshop on Algebras and CSPs (a part of
Summer Thematic Program on the Mathematics of Constraint Satisfaction
at the Fields Institute), Toronto, Canada.
[ Slides ]
 June 2011  The Dichotomy for Conservative Constraint Satisfaction
Problems Revisited at LICS 2011, Toronto, ON, Canada.
[Slides]
 March 2011  Applications of the Constraint Satisfaction
Problem to Universal Algebra at AMS Spring Central Section Meeting, Iowa City, IA, USA.
[Slides]
 June 2010  Rectangularity Theorem for Conservative Algebras at 80th Arbeitstagung Allgemeine Algebra, Bedlewo, Poland.
[Slides]
 October 2009  Constraint Satisfaction Problems of Bounded Width at FOCS 2009, Atlanta, GA, USA.
[Slides]
 September 2009  Congruence distributivity and near unanimity at Summer School on Algebra and Ordered Sets 2009, Stara Lesna, Slovakia.
 June 2009  Cyclic terms for join semidistributive varieties I , 78th Arbeitstagung Allgemeine Algebra, Bern, Switzerland.
My [slides], Marcin's
[slides] for the second part.
 June 2009  O slozitosti Hbarveni digrafu (in Czech) , STTI 2009, Prague, Czech Republic.
[Slides]
 May 2009  CSPs of Bounded Width II at CanaDAM 2009, Montreal, Canada.
Marcin's [slides] for the first part,
my [slides]
 September 2008  The algebraic approach to CSP
at Fall School of Logic & Complexity, Prague, Czech Republic.
 May 2008  CSP and NU(4)
at 76th Workshop on General Algebra, Linz, Austria.
[Slides]
 September 2007  Modularity and coloring of terms by variables
at 45th Summer School on General Algebra and Ordered Sets, Tale, Slovakia.
[Slides]
 July 2007  Jónsson terms imply cyclic terms for finite algebras
at Algorithmic Complexity and Universal Algebra, Szeged, Hungary.
[Slides]
 June 2007  Set functors determined by values on objects at
International Conference on Order, Algebra, and Logics, Nasville, USA.
[Slides]
 February 2007  Baskets of essentially algebraic categories at
73rd Arbeitstagung Allgemeine Algebra, Klagenfurt, Austria.
[Slides]
 November 2006  Clones are comprehensive at ECC meeting, Telc,
Czech Republic.
 September 2006  The category of varieties is alguniversal at
44th Summer School on General Algebra and Ordered Sets, Radejov, Czech Republic.
[Slides]
 February 2006  Algebraic universality of set endofunctors at
71st Arbeitstagung Allgemeine Algebra, Bedlewo, Poland.
[Slides]
 June 2004  Axioms for concrete categories at
Week of Doctoral Students, Prague, Czech Republic.
SEMINAR TALKS
 May 2021, CSPs and Symmetries,
Symmetry in New Castle seminar,
The University of Newcastle, Australia (online).
 Feb 2021, Finitely tractable PCSPs,
Ulam Seminar, CU Boulder, USA.
[Slides]
[Video]
 Oct 2020, CSPs and Symmetries,
19th Jarnik lecture, Prague, Czechia.
[Slides]
 July 2020  Baby PCP Theorem and reductions between Promise CSPs at
Online CSP seminar.
[Slides]
[Video]
 October 2019  Mathematics in coloring problems with promises at Palacky Universty, Olomouc, Czechia.
 November 2017  Promise Constraint Satisfaction Problem at TU Wien, Austria.
 November 2014  The CSP basics revisited at McMaster University, Hamilton, ON, Canada.
 November 2012  The dichotomy for constraint satisfaction problems at Colloquium on Mathematics, Masaryk University, Brno, Czech Republic.
 November 2012  Constraint satisfaction problem, decision and optimisation at Paris 7, France.
 May 2012  Robust algorithms for CSPs at University of Denver, CO, USA.
 February 2012  The complexity of CSPs at McMaster University, Hamilton, ON, Canada.
 October 2011  Robust approximation of constraint satisfaction problems at McMaster University, Hamilton, ON, Canada.
 July 2011  Categories and Magic Taylor at Fields Institute, Toronto, ON, Canada.
 October 2010  The complexity of constraint satisfaction problems at McMaster University, Hamilton, ON, Canada.
 February 2010  Absorption at Vanderbilt University, Nashville, TN, USA.
 September 2009  Finitely related algebras generating a congruence
distributive variety at University of Szeged, Hungary.
 December 2008  Constraint satisfaction problems of bounded width at Jagiellonian University in Krakow, Poland.
 November 2008  Meet semidistributivity has bounded width at University of Szeged, Hungary.
 December 2007  The algebraic approach to CSP, recent progress at Jagiellonian University in Krakow, Poland.
 November 2007  The algebraic approach to the constraint satisfaction problem, recent progress at University of Linz, Austria.
Talks on local seminars (KAFKA,
Algebra seminar,
Seminar on general mathematical structures, and others) are not listed.
GRANT PARTICIPATION
 20182022 ERC CoG 771005 30156/18269  CoCoSym: Symmetry in Computational Complexity (PI L. Barto)
 20182023 UNCE SCI/022  Methods of Algebra and Logic (PI J. Krajicek)
 20182020 GACR 1820123S 30113/201846  Expanding the Scope of Universal Algebra (PI M. Pinsker)
 20132017 GACR 1301832S 30113/201243  General algebra and its connections to computer science (PI L. Barto)
 20132014 7AMB 13P10 13 30129/221083  General algebra and applications (PIs D. Stanovsky, MFF UK, A. ZamojskaDzieno, Politechnika Warszawska)
 20092011 GACR 201/09/P223 30113/201710  Constraint Satisfaction Problem and Universal Algebra (PI L. Barto)
 20092010 MEB 040915 30129/221029  Graph, Grupoids and Algorithms (PIs J. Jezek, MFF UK; M. Maroti, University of Szeged)
 20082009 MEB 050817 30129/221002  An Algebraic Approach to the Constraint Satisfaction Problem (PIs J. Tuma, MFF UK; P. Idziak, Jagiellonian University, Krakow)
 2007 LC 505 ECC 30129/248001 VZ 30003/206099  Eduard Cech Center
 20062008 GACR 201/06/0664  Categorical methods in structural mathematics (PI M. Demlova, CVUT Praha)
 20022004 GACR 201/02/0148  Categorical methods in informatics and structural mathematics (PI M. Demlova, CVUT Praha)
EVENTS I (CO)ORGANIZED
 2018
[56th Summer School on Algebra and Ordered Sets], member of the organizing quarumvirate
 2016
[92th Arbeitstagung Allgemeine Algebra], organizer (with P. Jedlicka, D. Stanovsky)
 2015
[53rd Summer School on Algebra and Ordered Sets], organizer (with D. Stanovsky)
 2014
[Conference on Algebras and Clones (Algebras & Clones fest)], organizer (with D. Stanovsky)
 2011
[Summer Thematic Program on the Mathematics of Constraint Satisfaction
at the Fields Institute, Toronto], organizer (with A. Krokhin and R. Willard) of the Workshop on Algebra and CSPs
 2010
[International Conference on Algebras and Lattices (Jardafest)], member of the organizing triumvirate
 2008
[46th Summer School on Algebra and Ordered Sets], member of the organizing quadrumvirate
OTHERS
 Editor of Algebra Universalis
 PC member of STACS 2022
RESEARCH VISITS (SINCE 2017)
 Oct 6  Oct 7, 2019, Palacky University, Olomouc, Czechia (M. Botur)
 Feb 10  Feb 16, 2019, Jagiellonian University, Krakow, Poland (M. Kozik, M. Olsak)
 May 6  May 11, 2018, Durham University, UK (A. Krokhin).
 Feb 25  Mar 3, 2018, Jagiellonian University, Krakow, Poland (M. Kozik).
 Nov 23  Nov 24, 2017, TU Wien (M. Pinsker and postdocs)
 Jun 2  Jun 8, 2017, Jagiellonian University, Krakow, Poland (M. Kozik).
