52 citations · 146 across the 26 of their papers we have counts for
4 papers · 1 filter
Approximate counting CSP seen from the other side
Andrei A. Bulatov, Stanislav Zivny
In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(,-), in which the goal is, given a relational structure $\ma…
Counting Homomorphisms Modulo a Prime Number
Amirhossein Kazeminia, Andrei A. Bulatov
Counting problems in general and counting graph homomorphisms in particular have numerous applications in combinatorics, computer science, statistical physics, and elsewhere. One o…
Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model
Oleksii Omelchenko, Andrei A. Bulatov
The Random Satisfiability problem has been intensively studied for decades. For a number of reasons the focus of this study has mostly been on the model, in which instances are sam…
Concentration inequalities for sums of random variables, each having power bounded tails
Oleksii Omelchenko, Andrei A. Bulatov
In this work we present concentration inequalities for the sum of independent integer-valued not necessary indentically distributed random variables, where each variable has…