Showing 2026Show all
2 papers · 1 filter
math.CO2026
Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width
Matthias Lanzinger, Timo Camillo Merkl, Dan Suciu
We describe one explicit simple graph G on 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, e…
cs.DB2026
Convolution Sum-Product Queries
Kyle Deeds, Timo Camillo Merkl, Dan Suciu
We study query evaluation for an extension of sum-product queries (SPQ) that allows atoms with linear combinations of variables (e.g. ), which we call convolution…