Speaker
Description
Austen Z. Fan, Paraschos Koutris and Hangdong Zhao
Abstract: 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 \emph{semiring-oblivious} reduction from the $k$-clique problem to any query structure (hypergraph). Our reduction uses the notion of {\em embedding} a graph to a hypergraph, first introduced by Marx~\cite{Marx13}. 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 {\em 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.