Testing Unsatisfiability of Constraint Satisfaction Problems via Tensor
  Products
  We study the design of stochastic local search methods to prove
unsatisfiability of a constraint satisfaction problem (CSP). For a binary CSP,
such methods have been designed using the microstructure of the CSP. Here, we
develop a method to decompose the microstructure into graph tensors. We show
how to use the tensor decomposition to compute a proof of unsatisfiability
efficiently and in parallel. We also offer substantial empirical evidence that
our approach improves the praxis. For instance, one decomposition yields proofs
of unsatisfiability in half the time without sacrificing the quality. Another
decomposition is twenty times faster and effective three-tenths of the times
compared to the prior method. Our method is applicable to arbitrary CSPs using
the well known dual and hidden variable transformations from an arbitrary CSP
to a binary CSP.
