Papers for

database system designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Exponential size gap found between two logic query languages

An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations

Abstract: Three-variable first-order logic (FO3) and the calculus of relations (CoR) define the same binary queries, an equivalence going back to Tarski in the 1940s. While the classical translation $\text{FO3} \Rightarrow \text{CoR}$ is exponential, we prove that this blow-up is unavoidable, resolving a long-standing open question. We construct positive formulas $\varphi$ with a single quantifier whose equivalent terms require size $2^{Ω(|\varphi|)}$, even over finite structures and circuit representations with subterm sharing. Our proof uses a preservation argument over a single finite structure. This approach applies beyond our primary question, establishing the lower bound even for size-specific circuits and bounded-error randomized circuits, and yielding an analogous exponential gap for the matrix query language MATLANG.

Tue 22 SeptLogic in Computer ScienceComputational Complexity
The gist
Some ways of describing database queries use different logical languages. The authors show that when you switch from one language called three-variable logic to another called the calculus of relations, the descriptions can get exponentially larger. This means that certain logical expressions become much more complex and longer when translated between these languages. Their proof works even on small or finite data and applies to related query systems too.
Open → 2609.26778v1

Compressed subsequence checking is computationally hard even on two letters

Compressed Subsequence Checking is PSPACE-complete

Abstract: It is shown that the (scattered) subsequence problem for two words represented by straight-line programs is PSPACE-complete, even over a binary alphabet. The lower bound is obtained by a polynomial-time reduction from quantified subset sum.

Sun 13 SeptFormal Languages and Automata Theory
The gist
The problem of checking if one sequence appears scattered within another can be tricky when the sequences are stored in compressed forms. The authors show that deciding this is as tough as the hardest problems known in a complexity class called PSPACE, meaning it likely requires a lot of computational resources. This holds true even when the sequences only use two letters. They reached this conclusion by relating the problem to a well-known challenging problem called quantified subset sum.
Open → 2609.14490v1

Algorithm tests binary rank of matrices with fewer queries

Testing the Binary Rank with Polynomial Query Complexity

Abstract: We provide an adaptive two-sided error testing algorithm for the binary rank of a $0,1$ matrix $M$ with query complexity $O(d^3\log(d+1)/ε^2)$, where $d$ is the tested binary rank bound and $ε$ is the distance parameter. This answers an open question posed by Parnas, Ron and Shraibman~\cite{parnas2021property}, who asked whether the binary rank can be tested with query complexity polynomial in $d$ and $1/ε$. Furthermore, our testing algorithm can be used to find an approximate binary decomposition of $M$ with an additional $d(n+m)$ queries. That is, under the promise that the binary rank of $M$ is at most $d$, we show how to find, with probability at least $5/6$, two $0,1$ matrices $A',B'$ such that $M' = A' \cdot B'$ is a $0,1$ matrix which differs from $M$ on at most an $O(ε)$ fraction of its entries.

Wed 9 SeptData Structures and AlgorithmsDiscrete Mathematics
The gist
Figuring out the complexity of a matrix made of zeros and ones is a tricky problem. The authors created a new method that can quickly check if the matrix’s binary rank is below a certain limit. Their method works by only looking at a small part of the matrix, rather than the entire thing. If the matrix fits the limit, the method can also help build a close approximation of it.
Open → 2609.10496v1