Papers on Constraint Satisfaction and Complexity Theory

• 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
  J. Comput. Syst. Sci. 78(2): 681-688 (2012)
  
  
  
• The complexity of weighted and unweighted #CSP.
  A.Bulatov, M.E.Dyer, L.A.Goldberg, M.Jalsenius, M.Jerrum, D.Richerby
  J. Comput. Syst. Sci. 78(2): 681-688 (2012)
  
  
  
• Counting Problems and Clones of Functions.
  A.Bulatov, A.Hedayaty
  Multiple-Valued Logic and Soft Computing 18(2): 117-138 (2012)
  
  
  
• Complexity of conservative constraint satisfaction problems.
  A.Bulatov
  ACM Trans. Comput. Log. 12(4): 24 (2011)
  
  
  
• 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.
  
  
  
• Algebraic structures in combinatorial problems
  A.Bulatov and P.Jeavons
  submitted for publication
  
  
• 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.