Computer science and physics have been closely linked since the birth of modern
computing. In recent years, an interdisciplinary area has blossomed at the junction of these …

Tremendous progress has been made on algorithms for determining the satisfiability of
propositional formulas (SAT). In the last 10-15 years, speed-ups of many orders of …

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other
problems in NP) Page 1 M. Marin, L. Leustean (Eds.): 8th Symposium on Working Formal …

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 …

Let c> 0 be a constant, and Φ be a random Horn formula with n variables and m= c· 2n
clauses, chosen uniformly at random (with repetition) from the set of all nonempty Horn …

We study threshold properties of random constraint satisfaction problems under a
probabilistic model due to Molloy [Models for random constraint satisfaction problems, in …

In this paper we examine a variant, k-HSAT, of the well-known Satisfiability problem,
wherein formula instances are limited to CNF formulae having exactly k literals in each …

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 …

We begin by establishing the strong Hanani-Tutte Theorem on the projective plane. Namely
we show that if a graph can be drawn in the projective plane so that every two non-adjacent …

Random Horn Formulas and Propagation Connectivity for Directed Hypergraphs Page 1
Discrete Mathematics and Theoretical Computer Science DMTCS vol. 14:2, 2012, 29–36 …