c182ec594f38926b7fcb827635b9a8f4-Supplemental-Conference.pdf

Let q(Y;Θ) and cK(Y,X) be two smooth, decomposable circuits that are compatible overY then computing their product as a circuit rΘ,K(X,Y) = q(Y;Θ) cK(Y,X) that is decomposable overY can be done inO(|q||c|). Letr(X,Y)beacircuitthat is smooth and decomposable and deterministic overY then for a configurationx its MAP state argmaxyr(x,y)canbecomputedintimeO(|r|). For our experiments we use standard compilation tools toobtain aconstraint circuit starting from a propositional logical formula in conjunctive normal form. We now illustrate step-by-step one example of such a compilation for a simple logical formula. Deterministic sum units representdisjoint solutions to the logical formula, meaning there exists distinct assignments, characterized by the children, that satisfy the logical constraint e.g.