4 citations · 5 across the 3 of their papers we have counts for
4 papers
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas
Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos +1
We compute the probability of satisfiability of a class of random Horn-SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular,…
Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems
Gabriel Istrate
We study threshold properties of random constraint satisfaction problems under a probabilistic model due to Molloy. We give a sufficient condition for the existence of a sharp thre…
Phase Transitions and all that
Gabriel Istrate
The paper (as posted originally) contains several errors. It has been subsequently split into two papers, the corrected (and accepted for publication) versions appear in the archiv…
The phase transition in random Horn satisfiability and its algorithmic implications
Gabriel Istrate
Let c>0 be a constant, and be a random Horn formula with n variables and clauses, chosen uniformly at random (with repetition) from the set of all nonempty Hor…