Selected Publications

2013

  • A. A. Bulatov, Víctor Dalmau, Marc Thurley. Descriptive Complexity of Approximate Counting CSPs. CSL, 2013: 149-164
  • A. A. Bulatov. Boolean Max-Co-Clones. ISMVL 2013: 192-197
  • H. Dell, V. Kabanets, D. van Melkebeek, O. Watanabe. Is Valiant-Vazirani's Isolation Probability Improvable? Computational Complexity, 22(2): 345-383 (2013)
  • R. Chen, V. Kabanets, A. Kolokolova, R. Shaltiel, D. Zuckerman. Mining Circuit Lower Bound Proofs for Meta-Algorithms. Electronic Colloquium on Computational Complexity (ECCC), 20: 57 (2013)

2012

  • A. A. Bulatov, V. Dalmau, M. Grohe, D. Marx. Enumerating Homomorphisms. J. Comput. Syst. Sci., 78(2): 638-650 (2012)
  • A. A. Bulatov, M. E. Dyer, L. A. Goldberg, M. Jalsenius, M. Jerrum, D. Richerby. The Complexity of Weighted and Unweighted #CSP. J. Comput. Syst. Sci., 78(2): 681-688 (2012)
  • A. A. Bulatov, Martin E. Dyer, L. A. Goldberg, M. Jerrum. Log-supermodular Functions, Functional Clones and Counting CSPs. STACS 2012: 302-313
  • R. Impagliazzo, V. Kabanets, A. Wigderson. New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput., 41(6): 1722-1768 (2012)
  • R. Chen, V. Kabanets. Lower Bounds against Weakly Uniform Circuits. Electronic Colloquium on Computational Complexity (ECCC), 19: 7 (2012)
2011

  • A. A. Bulatov. Complexity of Conservative Constraint Satisfaction Problems. ACM Trans. Comput. Log., 12(4): 24 (2011)
  • A. A. Bulatov, D. Marx. Constraint Satisfaction Parameterized by Solution Size. ICALP, (1) 2011: 424-436

2010

  • R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Wigderson. Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput., 39(4): 1637-1665 (2010)
  • R. Impagliazzo, V. Kabanets. Constructive Proofs of Concentration Bounds. APPROX-RANDOM, 2010: 617-631
  • A. A. Bulatov, D. Marx. Constraint Satisfaction Problems and Global Cardinality Constraints. Commun. ACM, 53(9): 99-106 (2010)


2009

  • R. Impagliazzo, V. Kabanets, A. Wigderson. New Direct-product Testers and 2-query PCPs. STOC, 2009: 131-140
  • R. Impagliazzo, V. Kabanets, A. Kolokolova. An Axiomatic Approach to Algebrization. STOC, 2009: 695-704
  • A. A. Bulatov, V. Dalmau, M. Grohe, A. Marx. Enumerating Homomorphisms. STACS, 2009: 231-242
  • A. A. Bulatov, M. E. Dyer, L. A. Goldberg, M. Jalsenius, D. Richerby. The Complexity of Weighted Boolean #CSP with Mixed Signs. Theor. Comput. Sci., 410(38-40): 3949-3961 (2009)