We consider the fault diagnosis problem: how to use parallel testing rounds to identify which processors in a set are faulty. We prove that 4 rounds suffice when 3% or less of the processors are faulty, and 4 rounds are necessary when any nontrivial constant fraction of the processors are ... more >>>

We study a model of graph related formulae that we call the \emph{Constraint-Graph model}. A constraint-graph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge $e$ is labeled by a distinct Boolean variable and every vertex is associate with a Boolean function over ... more >>>