CS Paper Radar

Convolution Sum-Product Queries

Kyle Deeds, Timo Camillo Merkl, Dan Suciu

cs.DB ·submitted 2026-09-03 11:08 UTC · v2

Abstract

We study query evaluation for an extension of sum-product queries (SPQ) that allows atoms with linear combinations of variables (e.g. $A(2X+3Y-Z, Y+Z)$), which we call convolution sum-product queries (CSPQs). These queries arise in both practical settings (e.g. image processing workloads) and theoretical ones (e.g. the $(\min,+)$-convolution and $k$-SUM conjectures), and capture SPQs with added linear equality constraints. While prior work has considered the impact of linear in- and dis-equality constraints on query evaluation, the techniques developed in that setting are asymptotically sub-optimal for CSPQs. To address this, we describe several evaluation algorithms for CSPQs that leverage linear algebra techniques like rank analysis, quotient spaces, and variable substitution. First, we adapt Worst-Case Optimal Joins to CSPQs, achieving a runtime similar in spirit to that for conjunctive queries. Then, we extend the definition of tree decompositions (TDs) to CSPQs, and describe a factorized execution. In this extension, linear combinations are first-class citizens and play the same role as variables in traditional TDs. We define three width measures that bound the complexity of this execution with respect to the size of the domain values, of the active domain, and of the relation's support. Lastly, we show how these methods can be applied to arbitrary fields beyond the rationals.

Closest papers

Nearest neighbours by meaning across the whole index.

Min-Plus Convolution Lower Bounds via a Higher-Order BSG Theorem

cs.DS ·2026-10-07 ·Nick Fischer, Ce Jin, Yinzhan Xu
top venuetheory similarity 0.62
Abstract · Appears at FOCS '26

Min-Plus Convolution is a central problem in fine-grained complexity, and the associated Min-Plus Convolution Hypothesis forms the basis for a wide range of conditional lower bounds for fundamental problems. It is closely connected to the APSP and 3SUM Hypotheses, and in fact implies both, making it a unifying hypothesis for two of the main pillars of the area. In this work we establish several strong results related to Min-Plus Convolution. We design a universe reduction, showing, under a plausible additive combinatorics assumption, that the Min-Plus Convolution Hypothesis is equivalent to the Strong Min-Plus Convolution Hypothesis. We also obtain tight conditional lower bounds for multiple long-standing problems, including Min-Max Convolution and Bounded Monotone Min-Plus Convolution. Our approach is inspired by Fischer's recent equivalence between several variants of APSP [STOC '26], but extending that technique to the arithmetic setting requires overcoming deep obstacles. To this end, we develop a novel additive structure theorem that can be viewed as a higher-order substitute of the Balog-Szemerédi-Gowers (BSG) theorem, allowing us to extract strong additive structure even from weakly structured sets. Building on this structural result, we show that certain structured 3SUM instances (namely, sets with low rank) can be solved in truly subquadratic time. This algorithm forms the main algorithmic ingredient in our reductions. Besides, it generalizes all previously known truly subquadratic-time special cases of 3SUM, and is therefore of independent interest.

0.50

Optimal Encodings for Next/Previous Larger/Smaller Value Queries: A Unified Approach

cs.DS ·2026-10-28 ·Seungbum Jo, Geunho Kim, Kunihiko Sadakane, Srinivasa Rao Satti
similarity 0.61
Abstract

Given a 1D array over a total order and a query position in the array, a next larger value query returns the nearest position to the right whose value is larger than the value at the query position. Next smaller value queries and previous larger/smaller value queries are defined analogously. These queries are closely related to the $k$-th range minimum/maximum problem, which asks for the position of the $k$-th leftmost minimum/maximum value when the query range contains multiple minimum/maximum values. In this paper, we consider the encoding problem for answering any arbitrary subfamily of these four queries, where the queries must be answered without accessing the input array. We give a unified approach for obtaining space lower bounds for such encodings. We also obtain data structures for the query subfamilies that match the lower bounds up to lower-order additive terms, while supporting the queries in constant time. Our results generalize and improve several previous results on this problem [Gawrychowski and Nicholson, ICALP-2015; Jo and Satti, TCS-2016; Tsur, IPL-2019; Jo and Kim, Algorithmica-2025]. In addition, these results give tight bounds on the encoding complexity of all subfamilies of these queries for (1) permutations, (2) arrays without consecutive equal elements, and (3) general arrays.

0.19

Systematic Data Structure Lower Bounds via the Query-with-Sketch Model

cs.DS cs.CC ·2026-09-16 ·Sumegha Garg, Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang
published similarity 0.61
Abstract · CCC 2026

We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in\mathbb{R}^{n\times n}$ and parameters $k$ and $α$, the goal is to preprocess $\mathbf{M}$ so as to answer entry queries $(u,v)\mapsto \mathbf{M}^{k}[u,v]$ up to additive error $1/n^α$. We focus on AMP in the succinct and systematic regime, in which the data structure stores $\mathbf{M}$ verbatim, uses an additional $r$ bits of redundancy, and must answer queries by probing only a small number of entries of $\mathbf{M}$. Our main conceptual contribution is a general framework for proving probe--redundancy trade-offs for systematic data structures. We introduce the query-with-sketch model and develop a min-entropy-based approach that lifts conditional min-entropy bounds in the absence of redundancy to probe lower bounds in the presence of redundancy. We then establish these min-entropy bounds using problem-specific analytic and algebraic tools, for the downstream applications to AMP and its variants. As a consequence, our results provide new unconditional evidence toward a conjecture of Patrascu and Roditty (2010) on the space required for constant-time set-disjointness queries.

0.26

Guanaco: A Global-Uniformity Algorithm for Near-Submodular-Width Conjunctive Query Evaluation

cs.DB cs.DS ·2026-10-04 ·Mahmoud Abo Khamis, Hubie Chen
similarity 0.61
Abstract

We present Guanaco, an algorithm for performing conjunctive query evaluation where, for each Boolean conjunctive query, and positive epsilon, the algorithm achieves polynomial time with exponent equal to the submodular width plus epsilon. The algorithm and its running time generalize smoothly to general conjunctive queries. We believe the algorithm and its analysis to be notably simple, indeed, together we believe they form a highly simple argument that conjunctive query evaluation can be performed in essentially submodular width time. In the case of Boolean conjunctive queries, the algorithm is based on interleaving three simple primitives: a subroutine for establishing a form of consistency; a subroutine for establishing global uniformity, which, briefly speaking, partitions relations as needed to control discrepancies between average degree and maximum degree; and, a simple step that joins pairs of existing relations to form new relations.

0.22

Upper Bounds for CSP Non-redundancy via Locally Decodable Codes

cs.DM cs.CCcs.ITmath.CO ·2026-10-28 ·Joshua Brakensiek, David Conlon, Venkatesan Guruswami, Xiaoyu He, Jiaxi Nie +2 more
similarity 0.60
Abstract · 24 pages

In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independent. In the last few years, CSP non-redundancy has found a number of applications including in query complexity, sparsification, kernelization and streaming. In this paper, we present a novel technique for upper-bounding the non-redundancy of some relations using locally decodable codes (LDCs) and locally correctable codes (LCCs). More precisely, known limitations on the structure of 2-query LDCs and LCCs can be translated into limitations on the size of certain non-redundant CSP instances. This technique builds on a technique used by Brakensiek and Guruswami [STOC 2025] to bound non-redundancy via techniques from matching vector codes. Using LDCs and LCCs, we give improved upper bounds on non-redundancy of the BCK predicate pioneered by Bessiere, Carbonnel, and Katsirelos [AAAI 2020] as well as its well-studied Boolean variant. We also give the first example of a Boolean predicate whose non-redundancy is provably not of the form $n^{k\pm o(1)}$ for some positive integer $k$.

0.12

A Fast Algorithm for Subspace Convolution

cs.DS cs.CC ·2026-11-09 ·Shlomo A. Perles, Omri Weinstein
theorycode/data similarity 0.60
Abstract · 35 pages, 2 figures. Code, experiments, and Lean 4 formalizations: https://github.com/shlomi-perles/subspace-convolution

A cornerstone result in Boolean lattice theory is the subset-zeta transform, which computes the $f$-weighted subset summation problem $(Z f)(B)=\sum_{A\subseteq B}f(A)$ for all $ B\subseteq[n]$ in $O(N \log N)$ additions instead of the naïve $O(3^n) = O(N^{\log_2 3})$, where $N=2^n$. This paper studies the algebraic analogue of this problem--the subspace summation problem--where subsets are replaced by linear subspaces in $\mathbb{F}_q^n$. Surprisingly, we show that this problem admits a similar $Θ_q(N_q \log N_q)$-time algorithm, where $N_q$ is the number of subspaces. This improves substantially (in both theory and practice) over lattice-based algorithms ([BHK+16, KKW16]), which are known to be optimal for addition-only algorithms over $\mathbb R$. We prove similar runtimes for inversion, rank-constrained sums and span convolution. We describe two main applications: Fast linear algebra on Grassmann graphs: Matrix--vector multiplication for arbitrary distance-invariant kernels on $N$-vertex Grassmann graphs in $O_q(N\log N)$ arithmetic operations, together with fast spectral projections and exact solutions of the corresponding linear systems. Graph coloring of low binary cut-rank graphs: An $n^{2^{r^2/4+O(1)}}$-time algorithm for computing the chromatic number and chromatic polynomial of an $n$-vertex graph, given a rank-decomposition of width $r$. We also give quantitative reductions from satisfiability and monotone constraint problems. Experiments show speedups in measured running time of up to $18$ over the covering-pair algorithm for the zeta transform, $190$ over Poisson summation for rank-constrained sums, and $22$ over the distance-matrix recurrence for Grassmann kernel multiplication. Lean 4 formalizations of the transform identities, arithmetic operation bounds, and graph-coloring constructions accompany the paper [PW26].

0.28

Tight Width Minimisation of Self-Join-Free Quantified Conjunctive Queries

cs.DB cs.LO ·2026-11-16 ·Hubie Chen, Fabio Mogavero, Sam M. Thompson
top venue similarity 0.58
Abstract · To appear at PODS 2027

Query minimisation is a classical problem in database theory and the width of a formula, defined as the maximum number of free variables over all subformulae, is a central measure for query evaluation. We study width minimisation for a subclass of quantified conjunctive queries (QCQs), namely self-join-free QCQs. For this subclass, we show that rewriting optimality coincides with semantic optimality: given a query $φ$, the minimum-width query obtainable from $φ$ by applying natural and established rewriting rules has minimum width among all first-order formulae logically equivalent to $φ$. As a consequence, the width of a self-join-free QCQ can be optimised by a logical-equivalence-preserving rewriting algorithm.

0.27

Approximation Algorithms for Product Query Optimization

cs.DS ·2026-11-18 ·Macéo Ottavy, Avijeet Ghosh, Pascal Koiran, Alantha Newman, François Schwarzentruber +2 more
theory similarity 0.58
Abstract

We study database query optimization for Cartesian products. This problem is equivalent to finding an optimal plan for multiplying non-negative integers. We call this problem multiplication ordering. We show that the problem has an FPTAS when the cost of a plan is the sum of all intermediate products; both in the case when the overall final product is counted and when it is not. We show that using the optimal solution to the well-known product partition problem does not always lead to an optimal plan, but we establish connections between the product partition and multiplication ordering problems. Finally, we prove that multiplication ordering is in PTIME (resp. \NP-complete) when integers are powers of a same base where the exponents are written in unary (resp. in binary).

0.37