Journal Papers

Papers on Constraint Satisfaction and Complexity Theory

• Dismantlability, connectedness, and mixing in relational structures.
  Raimundo Briceno, Andrei Bulatov, Victor Dalmau, Benoit Larose
  J. Comb. Theory, Ser. B 147: 37-70 (2021)
  
• Satisfiability threshold for power law random 2-SAT in configuration model.
  Oleksii Omelchenko, Andrei A. Bulatov
  Theor. Comput. Sci. 888: 70-94 (2021)
  
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin.
  Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivny
  J. Comput. Syst. Sci. 109: 95-125 (2020)
  
• Approximate Counting CSP Seen from the Other Side.
  Andrei A. Bulatov, Stanislav Zivny
  ACM Trans. Comput. Theory 12(2): 11:1-11:19 (2020)
  
• Constraint Satisfaction Problems over semilattice block Mal'tsev algebras.
  Andrei A. Bulatov
  Inf. Comput. 268 (2019)
  
• The Subpower Membership Problem for Finite Algebras with Cube Terms
  A. Bulatov, P. Mayr, A. Szendrei
  Logical Methods in Computer Science, 15:1 (2019)
  
• Constraint satisfaction problems: complexity and algorithms.
  A. Bulatov
  SIGLOG News 5(4): 4-24 (2018)
  
• Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?
  A. Bulatov, O. Karpova, A. Shur, K. Startsev
  Electr. J. Comb. 24(3): P3.35 (2017)
  
• Functional clones and expressibility of partition functions.
  A. Bulatov, L.A. Goldberg, M. Jerrum, D. Richerby, S. Zivny
  Theor. Comput. Sci. 687: 11-39 (2017)
  
• The subpower membership problem for semigroups.
  A. Bulatov, M. Kozik, P. Mayr, M. Steindl
  IJAC 26(7): 1435-1452 (2016)
  
• Conservative constraint satisfaction re-revisited.
  A. Bulatov
  J. Comput. Syst. Sci. 82(2): 347-356 (2016)
  
• Galois Correspondence for Counting Quantifiers.
  A. Bulatov, A. Hedayaty
  Multiple-Valued Logic and Soft Computing 24(5-6): 405-424 (2015)
  
• Constraint Satisfaction Parameterized by Solution Size.
  A. Bulatov, D. Marx
  SIAM J. Comput. 43(2): 573-616 (2014)
  
• The expressibility of functions on the boolean domain, with applications to counting CSPs.
  A. Bulatov, M.E.Dyer, L.A.Goldberg, M.Jerrum, C.McQuillan
  J. ACM 60(5): 32 (2013)
  
• The complexity of the counting constraint satisfaction problem.
  A.Bulatov
  J. ACM 60(5): 34 (2013)
  
• Enumerating homomorphisms.
  A.Bulatov, V.Dalmau, M.Grohe, D.Marx
  Journal of Computer Systems Science. 78(2): 2012, 638-650
  
• The complexity of weighted and unweighted #CSP.
  A.Bulatov, M.Dyer, L.Goldberg, M.Jalsenius, M.Jerrum, D.Richerby
  Journal of Computer Systems Science. 78(2): 2012, 681-688
  
• Counting Problems and Clones of Functions.
  A.Bulatov, A.Hedayaty
  Multiple-Valued Logic and Soft Computing 18(2), 2012, 117-138
  
• Complexity of conservative constraint satisfaction problems.
  A.Bulatov
  ACM Transactions in Computational Logic 12(4), 2011, paper 24
  
• The complexity of global cardinality constraints.
  A.Bulatov, D. Marx
  Logical Methods in Computer Science 6(4), 2010 paper 4.
  
• Constraint satisfaction problems and global cardinality constraints.
  A.Bulatov, D. Marx
  Commun. ACM 53(9), 2010, pp. 99-106.
  
• The complexity of constraint satisfaction games and QCSP.
  A.Bulatov, F. Borner, H. Chen, P. Jeavons, A. Krokhin
  Inf. Comput. 207(9), 2009, pp. 923-944.
  
• The complexity of weighted Boolean #CSP with mixed signs.
  A.Bulatov, M. Dyer, L. Goldberg, M. Jalsenius, D. Richerby
  Theor. Comput. Sci. 410(38-40), 2009, pp. 3949-3961.
  
• Affine systems of equations and counting infinitary logic
  A.Atserias, A.Bulatov and A.Dawar
  Theor. Comput. Sci. 410(18), 2009, pp. 1666-1683.
  
• Learning intersection-closed classes with signatures
  A.Bulatov, H.Chen and V.Dalmau
  Theor. Comput. Sci. 382(3), 2007, pp. 209-220.
  
• Towards a dichotomy theorem for the counting constraint satisfaction problem
  A.Bulatov and V.Dalmau
  Information and Computation, 205(5), 2007, pp. 651-678.
  
• Complexity of Maltsev Constraints
  A.Bulatov
  Algebra i Logika, 45(6), 2006. [Russian}
  
• Complexity of the counting constraint satisfaction problem
  A.Bulatov
  Proceedings of the Ural State University, 36(7), 2005, 67-82. [Russian]
  
• Mal'tsev constraints are tractable
  A.Bulatov and V.Dalmau
  SIAM J. on Computing, 36(1), 2006, 16-27.
  
• H-coloring dichotomy revisited
  A.Bulatov
  Theoretical Coputer Science, 349(1), 2005, 31-39.
  
• The complexity of partition functions
  A.Bulatov and M.Grohe
  Theoretical Coputer Science, 348(2-3), 2005, 148-186.
  
• Tractable Conservative Constraint Satisfaction problems
  A.Bulatov
  ACM Transactions on Computational Logic, submitted, 80pp.
  
• The complexity of Conservative Constraint Satisfaction Problem
  A.Bulatov
  Doklady Rossijskoj Akademii Nauk, 70(1), 2004, 597-599. [Russian]
  
• A dichotomy theorem for constraints on a three-element set
  A.Bulatov
  Journal of the ACM, 53(1), 2006, 66-120.
  
• Classifying the complexity of constraints using finite algebras
  A. Bulatov, A. Krokhin, and P. Jeavons
  SIAM Journal on Computing, 34(3), 2005, 720-742.
  
• Combinatorial problems raised from 2-semilattices
  A. Bulatov
  Journal of Algebra, 298(2), 2006, 321-339.
  

Conference Proceedings

• Satisfiability and Algorithms for Non-uniform Random k-SAT.
  Oleksii Omelchenko, Andrei Bulatov:
  AAAI 2021: 3886-3894
  
• Algebra of Modular Systems: Containment and Equivalence.
  Andrei Bulatov, Eugenia Ternovska
  AAAI 2021: 6235-6243
  
• Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP.
  Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk:
  LICS 2021: 1-13
  
• Symmetries and Complexity (Invited Talk).
  Andrei A. Bulatov
  ICALP 2021: 2:1-2:17
  
• Counting Homomorphisms in Plain Exponential Time.
  Andrei A. Bulatov, Amineh Dadsetan
  ICALP 2020: 21:1-21:18
  
• Dismantlability, Connectedness, and Mixing in Relational Structures.
  Raimundo Briceno, Andrei A. Bulatov, Victor Dalmau, Benoit Larose
  ICALP 2019: 29:1-29:15
  
• A short story of the CSP dichotomy conjecture.
  Andrei A. Bulatov
  LICS 2019: 1
  
• Counting Homomorphisms Modulo a Prime Number.
  Amirhossein Kazeminia, Andrei A. Bulatov
  MFCS 2019: 59:1-59:13
  
• Approximate Counting CSP Seen from the Other Side.
  Andrei A. Bulatov, Stanislav Zivny
  MFCS 2019: 60:1-60:14
  
• Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model.
  Oleksii Omelchenko, Andrei A. Bulatov
  SAT 2019: 53-70
  
• Constraint Satisfaction Problems: Complexity and Algorithms.
  A. Bulatov
  LATA 2018: 1-25
  
• A Dichotomy Theorem for Nonuniform CSPs.
  A. Bulatov
  FOCS 2017: 319-330 (Best paper award)
  
• Constraint satisfaction problems over semilattice block Mal'tsev algebras.
  A. Bulatov
  LICS 2017: 1-11
  
• Graphs of relational structures: restricted types.
  A. Bulatov
  LICS 2016: 642-651
  
• Phase Transition for Local Search on Planted SAT.
  A. Bulatov, E. Skvortsov
  MFCS (2) 2015: 175-186
  
• Inferring Attitude in Online Social Networks Based on Quadratic Correlation.
  C. Wang, A. Bulatov
  PAKDD (1) 2014: 139-150
  
• Approximating Highly Satisfiable Random 2-SAT.
  A. Bulatov, C. Wang
  SAT 2014: 384-398
  
• Descriptive complexity of approximate counting CSPs.
  A.Bulatov, V.Dalmau, M.Thurley
  CSL 2013: 149-164
  
• Boolean Max-Co-Clones.
  A.Bulatov
  ISMVL 2013: 192-197
  
• Greedy Algorithms, Ordering of Variables, and d-degenerate Instances.
  C.Wang, A.Bulatov
  ISMVL 2012, pp. 31-36
  
• Counting Quantifiers, Subset Surjective Functions, and Counting CSPs.
  A.Bulatov, A.Hedayaty
  ISMVL 2012, pp. 331-336
  
• Log-supermodular functions, functional clones and counting CSPs.
  A.Bulatov, M.Dyer, L.Goldberg, M.Jerrum
  STACS 2012, pp. 302-313
  
• Constraint Satisfaction Parameterized by Solution Size.
  A.Bulatov, D.Marx
  ICALP (1) 2011, pp. 424-436
  
• The complexity of global cardinality constraints
  A.Bulatov, D.Marx
  LICS 2009, pp. 343-352
  
• Enumerating Homomorphisms
  A.Bulatov, V.Dalmau, M.Grohe, D.Marx
  STACS 2009, pp. 231-242
  
• Counting problems and clones of functions
  A.Bulatov
  ISMVL 2009, pp. 1-6
  
• The complexity of the counting Constraint Satisfaction Problem
  A.Bulatov
  ICALP(1) 2008, pp. 646-661.
  
• Affine systems of equations and counting infinitary logic
  A.Atserias, A.Bulatov and A.Dawar
  ICALP 2007, pp. 558-570.
  
• On the power of k-consistency
  A.Atserias, A.Bulatov and V.Dalmau
  ICALP 2007, pp. 279-290.
  
• The Efficiency of Local Search
  A.Bulatov and E.Skvortsov
  In Proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing (SAT'06)
  Seattle, USA, 2006.
  
• Learnability of Relatively Quantified Generalized Formulas
  A.Bulatov, H.Chen and V.Dalmau
  In Proceedings of the 15th International Conference on Algorithmic Learning Theory (ALT'04)
  Padova, Italy, 2004.
  
• A graph of a relational structure and Constraint Satisfaction Problems
  A.Bulatov
  In Proceedings of the 19th IEEE Annual Symposium on Logic in Computer Science (LICS'04)
  Turku, Finland, 2004.
  
• The complexity of partition functions
  A.Bulatov and M.Grohe
  In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04)
  Turku, Finland, 2004.
  
• Towards a dichotomy theorem for the Counting Constraint Satisfaction Problem
  A. Bulatov and V. Dalmau
  In Proceedings of 44rd IEEE Symposium on Foundations of Computer Science (FOCS'03),
  Cambridge, USA.
  
• An Algebraic Approach to Multi-sorted Constraints
  A.Bulatov and P. Jeavons
  In Proceedings of 9th International Conference on Principles and Practice of Constraint Programming (CP'03),
  Kinsale, Ireland, 2003.
  
• Quantified Constraints: Algorithms and Complexity
  F. Borner, A. Bulatov, A. Krokhin, and P. Jeavons
  In Proceedings of the 17th International Workshop Computer Science Logic (CSL'03), LNCS 2803,
  Vienna, Austria, 2003, 58-70.
  
• Amalgams of Constraint Satisfaction Problems
  A.Bulatov and E.Skvortsov
  In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03),
  Acapulco, Mexico, 2003, 197-202.
  
• The complexity of Constraint Satisfaction: an algebraic approach
  F. Borner, A. Bulatov, A. Krokhin, and P. Jeavons
  In Proceedings of SMS NATO Meeting ``Structural theory of automata, semigroups and universal algebras''
  Montreal, Canada, 2003, to appear
  
• Tractable conservative constraint satisfaction problems
  A. Bulatov
  In Proceedings of the 18th IEEE Symposium on Logig in Computer Science (LICS,03)
  Ottawa, Canada, 2003, 321-330.
  
• Functions of multiple-valued logic and the complexity of constraint satisfaction
  A.Bulatov, A.Krokhin and P.Jeavons
  In Proceedings of 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL'02),
  Tokyo, Japan, 2003, 343-351.
  
• A dichotomy theorem for constraints on a three-element set
  A. Bulatov
  In Proceedings of 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02),
  Vancouver, Canada, 2002, 649-658.
  (The paper has been awarded A Best Paper award.)
  
• The complexity of maximal constraint languages
  A. Bulatov, A. Krokhin, and P. Jeavons
  in Proceedings of 33rd ACM Symposium on the Theory of Computing (STOC'01), Crete, Greece, 2001, 667-674.
  
• Finite semigroups imposing tractable constraints
  A. Bulatov, P. Jeavons, and M. Volkov
  Proceedings of the School on Algorithmic Aspects of the Theory of Semigroups and its Applications,
  Coimbra, Portugal, 2001,
  Semigroups, Algorithms, Automata and Languages,
  World Scientific, Singapore, 2002, 313-329.
  
• Constraint satisfaction problems and finite algebras
  A. Bulatov, A. Krokhin, and P. Jeavons
  in Proceedings of 27th International Colloquim on Automata, Languages and Programming (ICALP'00),
  Geneva, Switzerland, Lecture Notes in Computer Science 1853, 2000, 272-282.
  

Algebra and Clone Theory Papers

• The subpower membership problem for semigroups.
  A. Bulatov, M. Kozik, P. Mayr, M. Steindl
  IJAC 26(7): 1435-1452 (2016)
  
• Three-element Mal'tsev algebras
  A. Bulatov
  Acta Sci.\ Math.\ (Szeged), 72, 2006, 519-550.
  
• Conditions satisfied by clone lattices
  A. Bulatov
  Algebra Universalis, 46(1-2), 2001, 237-241.
  
• Clones containing the Mal'tsev operation of some groups
  A. Bulatov
  Multiple-Valued Logic, 8(2), 2002, 193-221.
  
• On the structure of clone lattices, II
  A. Bulatov, A. Krokhin, K. Safin, A. Semigrodskikh, and E. Sukhanov
  Multiple-Valued Logic, 7 (5-6), 2001, 379-389.
  
• Counting Mal'tsev clones on small sets
  A. Bulatov, and P. Idziak
  Discrete Mathematics, 268, 2003, 59-80.
  
• On the number of Mal'tsev algebras
  A. Bulatov
  Contributions to General Algebra 13, 2001, 41-54.
  
• Abstract properties of the class of intervals if lattices of closed classes
  A. Bulatov
  Diskretnaja Matematika, v.10, no.5, 2000.
  [Russian; Engl.\ transl.: Discrete Math. Appl. 10, 2000, No.5, 481-498].
  
• The number of subclones of submaximal clones on a 3-element set
  A. Bulatov, D. Lau, and B. Strauch
  accepted to Algebra Universalis.
  
• On one semigroup property of clones
  A. Bulatov
  Proceedings of the International Conference on Semigroups and their applications including Semigroup Rings, St.-Petersburg, Russia. St.-Petersburg, 1999, 63--66.
  
• Sublattices of the lattice of clones of functions on a 3-element set, II
  A. Bulatov
  Algebra i Logika, v.38, no.3, 1999, 269-295.
  [Russian; Engl.\ transl.: Algebra Logic 38(1999), No.3, 144-158].
  
• Sublattices of the lattice of clones of functions on a 3-element set, I
  A. Bulatov
  Algebra i Logika, v.38, no.1, 1999, 3--23.
  [Russian; Engl.\ transl.: Algebra Logic 38(1999), No.1, 1-11].
  
• Some infinite intervals in clone lattices
  A. Bulatov
  Discussiones Mathematicae. Algebra and Stochastic Methods, v.19, no.1, 1999, 63--74.
  
• Polynomial reducts of modules II. Algebras of primitive and nilpotent functions
  A. Bulatov
  Multiple-Valued Logic, 3, 1998, 173--193
  
• Polynomial reducts of modules I. Rough classification
  A. Bulatov
  Multiple-Valued Logic, 3, 1998, 135--154.
  
• Polynomial reducts of modules
  A. Bulatov
  Izvestia Vuzov. Matematika, 10(413), 1996.
  [Russian; Engl.\ transl.: Russian Math. (Iz. VUZ) 40(10), 1997, 73--76].
  
• On clones with distributive subclone lattice,
  A. Bulatov
  In: Proceedings of the Conference on Universal Algebra and Lattice Theory, Szeged, Hungary, July 1996, 3--4.
  
• Some complex sublattices of clones lattices
  A. Bulatov
  Algebra (Krasnoyarsk, 1993). Eds.: Yu. L. Ershov et al., de Gruyter Verlag, Berlin, 1996, 41-44.
  
• On the structure of clone lattices
  A. Bulatov, A. Krokhin, K. Safin, and E.Sukhanov
  General Algebra and Discrete Mathematics, eds.: K. Denecke, O. Lueders, Heldermann Verlag, Berlin, 1995, 27-34.
  
• Finite sublattices of clone lattices
  A. Bulatov
  Algebra i Logika, 33(5), 1994, 514-549.
  [Russian; engl.transl.: Algebra and Logic, 33(5), 287-306]
  
• Identities of lattices of closed classes
  A. Bulatov
  Diskr.\ Matematika, 4(4), 1992, 140--148.
  [Russian; Engl. transl.: Discrete Math.\ Appl. 6(6), 1993, 601--610].
  

Books and Chapters

• Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings.
  A. Bulatov, A.M. Shur (Eds.)
  Lecture Notes in Computer Science 7913, Springer 2013, ISBN 978-3-642-38535-3
  
• Dualities for constraint satisfaction problems
  A.Bulatov, A.Krokhin, and B.Larose
  Complexity of Constraints 2008: 93-124
  
• Recent results on the algebraic approach to the CSP
  A.Bulatov and M.Valeriote
  Complexity of Constraints 2008: 68-92
  
• Problems of entrance exams in mathematics in Ural State university
  A. Bulatov, A. Gein, M. Volkov, and E. Sukhanov
  Ural State university, Ekaterinburg, 1998, 96pp. [Russian].
  
• Algebra and Geometry (A textbook for computer science studets).
  A. Zamiatin, A. Bulatov, and B.M.Vernikov
  Ural State university, Ekaterinburg, 2002, 452pp. [Russian].

Technical Reports

• Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP..
  Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
  CoRR abs/2104.11808 (2021)
  
• Complexity classification of counting graph homomorphisms modulo a prime number.
  Andrei A. Bulatov, Amirhossein Kazeminia
  CoRR abs/2106.04086 (2021)
  
• Local structure of idempotent algebras I.
  Andrei A. Bulatov
  CoRR abs/2006.10239 (2020)
  
• Local structure of idempotent algebras II.
  Andrei A. Bulatov
  CoRR abs/2006.10239 (2020)
  
• Graphs of relational structures: restricted types.
  Andrei A. Bulatov
  CoRR abs/2006.11713 (2020)
  
• A dichotomy theorem for nonuniform CSPs simplified.
  Andrei A. Bulatov
  CoRR abs/2007.09099 (2020)
  
• On the Complexity of CSP-based Ideal Membership Problems.
  Andrei A. Bulatov, Akbar Rafiey
  CoRR abs/2011.03700 (2020)
  
• Approximate counting CSP seen from the other side.
  Andrei A. Bulatov, Stanislav Zivný
  CoRR abs/1907.07922 (2019)
  
• Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model.
  Oleksii Omelchenko, Andrei A. Bulatov
  CoRR abs/1905.04827 (2019)
  
• Long range actions, connectedness, and dismantlability in relational structures.
  Raimundo Briceo, Andrei Bulatov, Vctor Dalmau, Benoit Larose
  CoRR abs/1901.04398 (2019)
  
• Counting homomorphisms in plain exponential time.
  Andrei Bulatov, Amineh Dadsetan
  CoRR abs/1810.03087 (2018)
  
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin.
  Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivny
  CoRR abs/1804.04993 (2018)
  
• The Subpower Membership Problem for Finite Algebras with Cube Terms.
  Andrei A. Bulatov, Peter Mayr, gnes Szendrei
  CoRR abs/1803.08019 (2018)
  
• A dichotomy theorem for nonuniform CSPs.
  Andrei A. Bulatov:
  CoRR abs/1703.03021 (2017)
  
• Constraint Satisfaction Problems over semilattice block Mal'tsev algebras.
  Andrei A. Bulatov:
  CoRR abs/1701.02623 (2017)
  
• Graphs of finite algebras, edges, and connectivity.
  A. Bulatov
  CoRR abs/1601.07403 (2016)
  
• The subpower membership problem for semigroups.
  A. Bulatov, P. Mayr, M. Steindl
  CoRR abs/1603.09333 (2016)
  
• Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?
  A. Bulatov, O. Karpova, A. Shur, K. Startsev
  CoRR abs/1609.03199 (2016)
  
• Functional Clones and Expressibility of Partition Functions.
  A. Bulatov, L.A. Goldberg, M. Jerrum, D. Richerby, S. Zivny
  CoRR abs/1609.07377 (2016)
  
• Constraint satisfaction parameterized by solution size.
  A.Bulatov, D.Marx
  CoRR abs/1206.4854 (2012)
  
• Galois correspondence for counting quantifiers.
  A.Bulatov, A.Hedayaty
  CoRR abs/1210.3344 (2012)
  
• Log-supermodular functions, functional clones and counting CSPs.
  A.Bulatov, M.Dyer, L.Goldberg, M.Jerrum
  CoRR abs/1108.5288 (2011)
  
• The complexity of global cardinality constraints.
  A.Bulatov, V.Dalmau, M.Grohe, and D.Marx
  CoRR abs/1010.0201
  
• The complexity of weighted and unweighted #CSP.
  A.Bulatov, M.Dyer, L.Goldberg, M.Jalsenius, M.Jerrum, D.Richerby
  CoRR abs/1005.2678
  
• Enumerating Homomorphisms.
  A.Bulatov, V.Dalmau, M.Grohe, and D.Marx
  CoRR abs/0902.1256
  
• The Complexity of Weighted Boolean #CSP with Mixed Signs.
  A.Bulatov, M.Dyer, L.A.Goldberg, M.Jalsenius, D.Richerby
  CoRR abs/0812.4171
  
• Phase transition for Local Search on planted SAT.
  A.Bulatov, E.Skvortsov
  CoRR abs/0811.2546
  
• The complexity of the Counting Constraint Satisfaction Problem
  A.Bulatov
  ECCC, TR07-093, 2007, 29 p.
  
• Tractable conservative constraint satisfaction problems
  A. Bulatov
  Technical report PRG-RR-03-01, Oxford University, 2002, 75pp.
  
• Towards a dichotomy theorem for the Counting Constraint Satisfaction Problem
  A. Bulatov and V.Dalmau
  Technical report PRG-RR-03-13, Oxford University, 2003, 37pp.
  [Full version of FOCS'03 paper]
  
• Quantified constraints and surjective polymorphisms
  F. Borner, A. Bulatov, A. Krokhin, and P. Jeavons
  Technical report PRG-RR-02-11, Oxford University, 2002, 25pp.
  
• Tractable constraint satisfaction problems on a 3-element set
  A. Bulatov
  Technical report PRG-RR-02-06, Oxford University, 2002, 48pp.
  see also ECCC TR 03-032
  [Full version of FOCS'02 paper].
  
• Malt'sev constraints are tractable
  A. Bulatov
  Technical report PRG-RR-02-05, Oxford University, 2002, 36pp.
  see also ECCC TR 03-034
  
• The complexity of maximal constraint languages
  A. Bulatov, A. Krokhin, and P. Jeavons
  Technical report PRG-RR-01-03, Oxford University, 2001, 15pp.
  [Almost identical to STOC'01 paper]
  
• An algebraic approach to multi-sorted constraints
  A. Bulatov, and P. Jeavons
  Technical report PRG-RR-01-18, Oxford University, 2001, 21pp.
  
• Algebraic structures in combinatorial problems
  A. Bulatov, and P. Jeavons
  Technical report MATH-AL-4-2001, Technische Universitat Dresden, 2001, 32pp.
  submitted to International Journal of Algebra and Computing.
  
• Constraint satisfaction problems and finite algebras
  A. Bulatov, A. Krokhin, and P. Jeavons
  Technical report PRG-TR-4-99, Oxford University, 1999, 17pp.
  [Full version of ICALP'00 paper]
  
• Tractable constraints closed under a binary operation
  A. Bulatov, and P. Jeavons
  Technical report PRG-TR-12-00, Oxford University, 2000, 27pp.
  submitted for publication.