English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the fine-grained complexity of evaluating Boolean ConjunctiveQueries and their generalization to sum-of-product problems over an arbitrarysemiring. For these problems, we present a general semiring-oblivious reductionfrom the k-clique problem to any query structure (hypergraph). Our reductionuses 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 boundsfor many classes of hypergraphs, including cycles, Loomis-Whitney joins, somebipartite graphs, and chordal graphs. These lower bounds have a dependence onwhat we call the clique embedding power of a hypergraph H, which we believe isa quantity of independent interest. We show that the clique embedding power isalways less than the submodular width of the hypergraph, and present adecidable algorithm for computing it. We conclude with many open problems forfuture research.

The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems