  We study the fine-grained complexity of evaluating Boolean Conjunctive
Queries and their generalization to sum-of-product problems over an arbitrary
semiring. For these problems, we present a general semiring-oblivious reduction
from the k-clique problem to any query structure (hypergraph). Our reduction
uses the notion of embedding a graph to a hypergraph, first introduced by Marx.
As a consequence of our reduction, we can show tight conditional lower bounds
for many classes of hypergraphs, including cycles, Loomis-Whitney joins, some
bipartite graphs, and chordal graphs. These lower bounds have a dependence on
what we call the clique embedding power of a hypergraph H, which we believe is
a quantity of independent interest. We show that the clique embedding power is
always less than the submodular width of the hypergraph, and present a
decidable algorithm for computing it. We conclude with many open problems for
future research.
