Libor Barto

HOME RESEARCH FOR STUDENTS

Research interests: Universal algebra, computational complexity, in particular constraint satisfaction problems

IN PROGRESS

  1. L. Barto, M. Kozik, A. Bulatov, D. Zhuk, Structure of finite Taylor minimal algebras, in preparation
  2. L. Barto, L. Ham, M. Jackson, Flexible CSPs, in preparation
  3. L. Barto, M. Kompatscher, M. Olsak, M. Pinsker, T. Van Pham, Equations in oligomorphic clones and the constraint satisfaction problem for omega-categorical structures, in preparation [arXiv]
  4. L. Barto, M. Olsak, M. Pinsker, Topology is irrelevant, in preparation
  5. L. Barto, Accessible set endofunctors are universal, in preparation

BOOK CHAPTERS

  1. (survey) L. Barto, A. Krokhin, R. Willard, Polymorphisms, and how to use them, in "The Constraint Satisfaction Problem: Complexity and Approximability", Dagstuhl Follow-Ups, vol. 7, 1–44, 2017 [paper] [complete volume].
  2. (survey) L. Barto, M. Kozik, Absorption in Universal Algebra and CSP, in "The Constraint Satisfaction Problem: Complexity and Approximability", Dagstuhl Follow-Ups, vol. 7, 45–77, 2017 [paper] [complete volume].

JOURNAL PAPERS

  1. L. Barto, O. Draganov, The minimal arity of near-unanimity polymorphisms, submitted [arXiv]
  2. L. Barto, Finitely related algebras in congruence modular varieties have few subpowers, to appear in JEMS [preprint]

  3. L. Barto, J. Oprsal, M. Pinsker, The wonderland of reflections, Israel Journal of Mathematics (2017), online first [preprint] [DOI]

  4. L. Barto, J. Bulin, Deciding absorption in relational structures, Algebra Universalis 78/1 (2017), 3-18 [DOI] [arXiv]
  5. L. Barto, The collapse of the bounded width hierarchy, Journal of Logic and Computation 26/3 (2016), 923-943 [DOI] [preprint]
  6. L. Barto, A. Kazda, Deciding absorption, Int. J. Algebra Comput. 26/05 (2016), 1033-1060 [DOI] [arXiv]
  7. L. Barto, M. Kozik, Robustly solvable constraint satisfaction problems, SIAM Journal of Computing 45-4 (2016), 1646-1669 [DOI] [arXiv]
  8. (survey) L. Barto, The constraint satisfaction problem and universal algebra, The Bulletin of Symbolic Logic 21/03 (2015), 319-337. [DOI] [preprint]
  9. L. Barto, M. Kozik, D. Stanovsky, Mal'tsev conditions, lack of absorption, and solvability, Algebra Universalis 74/1-2 (2015), 185-206 [DOI] [preprint]
  10. L. Barto, M. Kozik, Constraint satisfaction problems solvable by local consistency methods, Journal of the ACM 61/1 (2014), 3:1-3:19 [DOI]
  11. L. Barto, J. Bulin, CSP dichotomy for special polyads, Int. J. Algebra Comput. 23/05 (2013), 1151-1174 [DOI] [preprint]
  12. L. Barto, Finitely related algebras in congruence distributive varieties have near unanimity terms, Canadian Journal of Mathematics 65/1 (2013), 3-21 [DOI] [preprint]
  13. L. Barto, M. Kozik, Absorbing subalgebras, cyclic terms and the constraint satisfaction problem, Logical Methods in Computer Science 8/1:07 (2012), 1-26. [preprint]
  14. L. Barto, D. Stanovsky, Polymorphisms of small digraphs, Novi Sad J. Math. 40/2 (2010), 95-109 [ paper & data ]
  15. L. Barto, M. Kozik, Cyclic terms for SD(v) varieties - revisited, Algebra Universalis 64/1-2 (2010), 137-142 [ DOI ], [preprint]
  16. L. Barto, M. Kozik, Congruence distributivity implies bounded width, SIAM Journal on Computing 39/4 (2009), 1531-1542 [preprint]
  17. L. Barto, M. Kozik, M. Maroti, R. McKenzie, T. Niven, Congruence modularity implies cyclic terms for finite algebras, Algebra Universalis 61/3 (2009), 365-380 [preprint]
  18. L. Barto, M. Kozik, M. Maroti, T. Niven, CSP dichotomy for special triads, Proc. Amer. Math. Soc. 137/9 (2009), 2921-2934. [preprint] [errata!]
  19. L. Barto, Slices of essentially algebraic categories, Applied Categorical Structures 17/2 (2009), 119-152. [preprint]
  20. 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 Bang-Jensen and Hell), SIAM Journal on Computing 38/5 (2009), 1782-1802. [preprint]
  21. L. Barto, The category of varieties and interpretations is alg-universal, Journal of Pure and Applied Algebra 211/3 (2007), 721-731. [preprint]
  22. L. Barto, Finitary set endofunctors are alg-universal, Algebra Universalis 57/1 (2007), 15-26. [preprint]
  23. L. Barto, P. Zima, Every group is representable by all natural transformations of some set-functor, Theory and Applications of Categories 14/13 (2005), 294-309. [download]
  24. L. Barto, Weakly terminal objects in quasicategories of set endofunctors, Applied Categorical Structures 13/3 (2005), 257-264. [preprint]

CONFERENCE PAPERS

  1. 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, 1-12. [DOI] [arXiv]
  2. 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, 615-622. [preprint]
  3. 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, 125-134. [preprint].
  4. L. Barto, M. Kozik, Robust satisfiability of constraint satisfaction problems, Proceedings of the 44th symposium on Theory of Computing, STOC'12 (2012), 931-940. [preprint]. Also published in ECCC, Report No. 163 (2011).
  5. L. Barto, The dichotomy for conservative constraint satisfaction problems revisited, Proceedings of the 26th IEEE Symposium on Logic in Computer Science, LICS'11, 301-310 [preprint]
  6. L. Barto, M. Kozik, New conditions for Taylor varieties and CSP, Proceedings of the 25th IEEE Symposium on Logic in Computer Science, LICS'10, 100-109 [ DOI ]
  7. 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), 595-603 [preprint]
  8. 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), 789-796.

OTHER PAPERS

  1. (survey) L. Barto, Constraint satisfaction problem and universal algebra, ACM SIGLOG News 1/2 (2014), 14-24. [PDF] [The whole issue]

THESES

  1. L. Barto, Full embeddings and their modifications, PhD thesis, Charles University in Prague, 2006 [PDF] [PS]
  2. L. Barto, Funktory blízké úplným vnořením, Master's thesis, Charles University in Prague, 2003 (in Czech)

LECTURE NOTES

  1. D. Stanovsky, L. Barto, Pocitacova algebra (Computer algebra), Matfyzpress, 2011

MISC

FUTURE TALKS

  1. June 2018 - TBA at Dagstuhl workshop The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany.

INVITED TALKS

  1. August 2017 - Equationally nontrivial algebras at BLAST, Nashville, TN, USA. [Slides]
  2. November 2016 - {Symmetry, Logic, CSP} at the workshop {Symmetry, Logic, Computation}, part of the programme Logical Structures in Computation, Berkeley, USA. [Slides]
  3. August 2016 - Infinite domain constraint satisfaction problem at CSL, Marseille, France. [Slides]
  4. 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]
  5. May 2015 - A rectangularity theorem for simple Taylor algebras at Open Problems in Universal Algebra , a Shanks workshop at Vanderbilt University, Nashville, USA.
  6. February 2015 - Weighted clones at 89th Arbeitstagung Allgemeine Algebra, Dresden, Germany. [Slides]
  7. May 2014 - Universal algebra and the constraint satisfaction problem at Association of Symbolic Logic North American Annual Meeting, Boulder, CO, USA. [Slides]
  8. September 2013 - Finitely related algebras at The 51st Summer School on General Algebra and Ordered Sets, Trojanovice, Czech Republic. [Slides]
  9. July 2013 - The distance from congruence distributivity to near unanimity at GAIA 2013: General Algebra and its Applications, Melbourne, Australia. [Slides]
  10. June 2013 - Prime Maltsev conditions at 4th Novi Sad Algebraic Conference, Novi Sad, Serbia. [Slides]
  11. June 2012 - The Valeriote conjecture at Conference on Universal Algebra and Lattice Theory, Szeged, Hungary. [Slides]
  12. March 2012 - Robust algorithms for CSPs at 83th Arbeitstagung Allgemeine Algebra, Novi Sad, Serbia. [Slides]
  13. June 2011 - Instances of the Constraint Satisfaction Problem in Universal Algebra at Second International Conference on Order, Algebra and Logics, Krakow, Poland. [Slides]
  14. 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.
  15. August 2009 - Prague Strategies at Novi Sad Algebraic Conference, Novi Sad, Serbia. [Slides]
  16. November 2008 - Constraint Satisfaction Problems of Bounded Width at Eduard Cech Center meeting, Trest, Czech Republic [Slides]

TUTORIALS

  1. September 2017 - Universal algebra today at 55th Summer School on Algebra and Ordered Sets, Novy Smokovec, Slovakia. [Slides I] [Slides II] [Slides III]
  2. September 2015 - Constraint satisfaction problem over a fixed template at Highlights of Logic, Games and Automata , Prague, Czech Republic. [Slides]

TALKS AT INVITATIONAL WORKSHOPS

  1. October 2015 - The CSP basics revisited at Dagstuhl workshop Duality in Computer Science Schloss Dagstuhl, Germany.
  2. July 2015 - CSPs over hereditarily semisimple algebra at Dagstuhl workshop The Constraint Satisfaction Problem: Complexity and Approximability , Schloss Dagstuhl, Germany.
  3. November 2014 - The basic CSP reductions revisited at BIRS Workshop Algebraic and Model Theoretical Methods in Constraint Satisfaction, Banff, Canada. [Slides]
  4. November 2012 - Robust Satisfiability of CSPs at the workshop The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany. [Slides]

OTHER CONFERENCE TALKS

  1. June 2017 - Cores of oligomorphic clones revisited at 94th Arbeitstagung Allgemeine Algebra + 5th Novi Sad Algebraic Conference, Novi Sad, Serbia.
  2. September 2016 - Local Loop Lemma at The 54th Summer School on General Algebra and Ordered Sets, Trojanovice, Czech Republic. [Slides]
  3. September 2014 - On simple Taylor algebras at 52nd Summer School on Algebra and Ordered Sets, Stara Lesna, Slovakia. [Slides]
  4. February 2012 - Decision, counting and optimisation in constraint satisfaction problems at A Gathering of Prague-Based Logicians, Prague, Czech Republic.
  5. September 2012 - Decidability of absorption for relational structures at 50th Summer School on Algebra and Ordered Sets, Novy Smokovec, Slovakia. [Slides]
  6. August 2011 - Robust approximation of CSPs at Workshop on Approximability of CSPs, Toronto, Canada.
  7. 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 ]
  8. June 2011 - The Dichotomy for Conservative Constraint Satisfaction Problems Revisited at LICS 2011, Toronto, ON, Canada. [Slides]
  9. March 2011 - Applications of the Constraint Satisfaction Problem to Universal Algebra at AMS Spring Central Section Meeting, Iowa City, IA, USA. [Slides]
  10. June 2010 - Rectangularity Theorem for Conservative Algebras at 80th Arbeitstagung Allgemeine Algebra, Bedlewo, Poland. [Slides]
  11. October 2009 - Constraint Satisfaction Problems of Bounded Width at FOCS 2009, Atlanta, GA, USA. [Slides]
  12. September 2009 - Congruence distributivity and near unanimity at Summer School on Algebra and Ordered Sets 2009, Stara Lesna, Slovakia.
  13. June 2009 - Cyclic terms for join semi-distributive varieties I , 78th Arbeitstagung Allgemeine Algebra, Bern, Switzerland. My [slides], Marcin's [slides] for the second part.
  14. June 2009 - O slozitosti H-barveni digrafu (in Czech) , STTI 2009, Prague, Czech Republic. [Slides]
  15. May 2009 - CSPs of Bounded Width II at CanaDAM 2009, Montreal, Canada. Marcin's [slides] for the first part, my [slides]
  16. September 2008 - The algebraic approach to CSP at Fall School of Logic & Complexity, Prague, Czech Republic.
  17. May 2008 - CSP and NU(4) at 76th Workshop on General Algebra, Linz, Austria. [Slides]
  18. September 2007 - Modularity and coloring of terms by variables at 45th Summer School on General Algebra and Ordered Sets, Tale, Slovakia. [Slides]
  19. July 2007 - Jónsson terms imply cyclic terms for finite algebras at Algorithmic Complexity and Universal Algebra, Szeged, Hungary. [Slides]
  20. June 2007 - Set functors determined by values on objects at International Conference on Order, Algebra, and Logics, Nasville, USA. [Slides]
  21. February 2007 - Baskets of essentially algebraic categories at 73rd Arbeitstagung Allgemeine Algebra, Klagenfurt, Austria. [Slides]
  22. November 2006 - Clones are comprehensive at ECC meeting, Telc, Czech Republic.
  23. September 2006 - The category of varieties is alg-universal at 44th Summer School on General Algebra and Ordered Sets, Radejov, Czech Republic. [Slides]
  24. February 2006 - Algebraic universality of set endofunctors at 71st Arbeitstagung Allgemeine Algebra, Bedlewo, Poland. [Slides]
  25. June 2004 - Axioms for concrete categories at Week of Doctoral Students, Prague, Czech Republic.
SEMINAR TALKS
  1. November 2014 - The CSP basics revisited at McMaster University, Hamilton, ON, Canada.
  2. November 2012 - The dichotomy for constraint satisfaction problems at Colloquium on Mathematics, Masaryk University, Brno, Czech Republic.
  3. November 2012 - Constraint satisfaction problem, decision and optimisation at Paris 7, France.
  4. May 2012 - Robust algorithms for CSPs at University of Denver, CO, USA.
  5. February 2012 - The complexity of CSPs at McMaster University, Hamilton, ON, Canada.
  6. October 2011 - Robust approximation of constraint satisfaction problems at McMaster University, Hamilton, ON, Canada.
  7. July 2011 - Categories and Magic Taylor at Fields Institute, Toronto, ON, Canada.
  8. October 2010 - The complexity of constraint satisfaction problems at McMaster University, Hamilton, ON, Canada.
  9. February 2010 - Absorption at Vanderbilt University, Nashville, TN, USA.
  10. September 2009 - Finitely related algebras generating a congruence distributive variety at University of Szeged, Hungary.
  11. December 2008 - Constraint satisfaction problems of bounded width at Jagiellonian University in Krakow, Poland.
  12. November 2008 - Meet semidistributivity has bounded width at University of Szeged, Hungary.
  13. December 2007 - The algebraic approach to CSP, recent progress at Jagiellonian University in Krakow, Poland.
  14. 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

  1. 2013-2017 GACR 13-01832S 301-13/201243 - General algebra and its connections to computer science
  2. 2013-2014 7AMB 13P10 13 301-29/221083 - General algebra and applications (D. Stanovsky, MFF UK, A. Zamojska-Dzieno, Politechnika Warszawska)
  3. 2009-2011 GACR 201/09/P223 301-13/201710 - Constraint Satisfaction Problem and Universal Algebra
  4. 2009-2010 MEB 040915 301-29/221029 - Graph, Grupoids and Algorithms (J. Jezek, MFF UK; M. Maroti, University of Szeged)
  5. 2008-2009 MEB 050817 301-29/221002 - An Algebraic Approach to the Constraint Satisfaction Problem (J. Tuma, MFF UK; P. Idziak, Jagiellonian University, Krakow)
  6. 2007 LC 505 ECC 301-29/248001 VZ 300-03/206099 - Eduard Cech Center
  7. 2006-2008 GACR 201/06/0664 - Categorical methods in structural mathematics (M. Demlova, CVUT Praha)
  8. 2002-2004 GACR 201/02/0148 - Categorical methods in informatics and structural mathematics (M. Demlova, CVUT Praha)

EVENTS I (CO-)ORGANIZED

  1. 2016 [92th Arbeitstagung Allgemeine Algebra], organizer (with P. Jedlicka, D. Stanovsky)
  2. 2015 [53rd Summer School on Algebra and Ordered Sets], organizer (with D. Stanovsky)
  3. 2014 [Conference on Algebras and Clones (Algebras & Clones fest)], organizer (with D. Stanovsky)
  4. 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
  5. 2010 [International Conference on Algebras and Lattices (Jardafest)], member of the organizing triumvirate
  6. 2008 [46th Summer School on Algebra and Ordered Sets], member of the organizing quadrumvirate

 

RESEARCH VISITS (SINCE 2017)

  1. June 2 - June 8, 2017, Jagiellonian University, Krakow, Poland (M. Kozik).