  We propose an algorithm for answering conjunctive queries with negation,
where the negated relations have bounded degree. Its data complexity matches
that of the best known algorithms for the positive subquery of the input query
and is expressed in terms of the fractional hypertree width and the submodular
width. The query complexity depends on the structure of the negated subquery;
in general it is exponential in the number of join variables occurring in
negated relations yet it becomes polynomial for several classes of queries.
  This algorithm relies on several contributions. We show how to rewrite
queries with negation on bounded-degree relations into equivalent conjunctive
queries with not-all-equal (NAE) predicates, which are a multi-dimensional
analog of disequality (not-equal). We then generalize the known color-coding
technique to conjunctions of NAE predicates and explain it via a Boolean tensor
decomposition of conjunctions of NAE predicates. This decomposition can be
achieved via a probabilistic construction that can be derandomized efficiently.
