Papers for

database system developers

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.

Graph decomposition methods compared for query processing speed

Separations Between Submodular-Like Graph Widths

Abstract: Many algorithmic frameworks exist for evaluating join queries. They range from simple ones, such as dynamic programming over a single tree decomposition, high-degree-low-degree splitting from graph algorithms, and the degree uniformization of Joglekar and Ré, to sophisticated ones based on information-theoretic inequalities, such as the PANDA framework for submodular width. Each of these frameworks except high-degree-low-degree splitting comes with a width notion of the query that determines its running-time exponent. We fill this gap by formalizing high-degree-low-degree splitting with $\ell$ degree classes, which gives rise to the degree-splitting width $\mathrm{ds}_\ell$-width. These width notions form a hierarchy, but it was not known whether the more complicated frameworks achieve better worst-case exponents than the simpler ones on any graph query. We study this question for full self-join-free join queries with binary relations, which amounts to colored subgraph isomorphism for a pattern graph $H$. We show that every inequality in the hierarchy $\mathrm{subw} \le \#\mathrm{subw} \le \text{m-width} \le \mathrm{ds}_\ell\text{-width}$ can be strict. For instance, $\text{m-width}(K_{3,3}) = 2 < \mathrm{ds}_\ell\text{-width}(K_{3,3})$ for every constant $\ell$, so no constant number of degree classes reaches the exponent of degree uniformization. We find the smallest separating patterns, with 8, 9, and 6 nodes, respectively, by an exhaustive search with a software tool that computes these widths via mixed integer linear programming. Along the way, we give a degree-based algorithm that removes the polylogarithmic overhead of degree uniformization when evaluating full join queries. Furthermore, we show that with logarithmically many degree classes, the degree-splitting width coincides with the m-width of Joglekar and Ré. Finally, we discuss several open problems.

Thu 12 NovData Structures and AlgorithmsDatabases
The gist
Evaluating large database queries efficiently depends on understanding the structure of their connections, often represented as graphs. The authors compare different ways to measure the complexity of these graphs, which correspond to how fast algorithms can run. They find that some newer, more intricate methods genuinely improve the speed of query evaluation on certain graph shapes, while simpler methods fall short. This helps clarify which approaches work best and when, guiding better algorithm design.
Open → 2611.17307v1

First-order model checking is efficient on monadically dependent graphs

First-Order Model Checking on Monadically Dependent Graph Classes

Abstract: Monadically dependent graph classes are those in which first-order logic cannot encode all graphs. They include all nowhere dense classes and all classes of bounded twin-width. We show that first-order model checking is fixed-parameter tractable on every monadically dependent graph class. Together with the known hardness result for hereditary classes that are not monadically dependent, this gives a complete characterization of the hereditary graph classes with fixed-parameter tractable first-order model checking. This resolves a central open problem in algorithmic model theory. Our proof combines ideas from structural graph theory (graph decompositions), finite model theory (locality of first-order logic), and model theory (counting types). In particular, we show that in monadically dependent classes, tuples of fixed length have only $|U|^{O(1)}$ types of fixed quantifier rank over any set of parameters $U$.

Thu 5 NovLogic in Computer ScienceDiscrete MathematicsData Structures and Algorithms
The gist
Some graphs are easier to analyze with logical rules than others. The authors found a clear boundary between types of graphs where checking certain conditions quickly is possible, and where it is hard. They showed that a large and important class of graphs called monadically dependent graphs can be handled efficiently by first-order model checking. This answers a long-standing question about which graph classes allow quick logical queries.
Open → 2611.08143v1

Algorithms improve clustering accuracy with less memory in streaming data

Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering

Abstract: We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(ε^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk, Lin, Woodruff, Yu, and Zhou, FOCS 2026], and is furthermore the first algorithm whose space is linear in $kd$, even in the oblivious (non-adaptive) setting. We develop several new techniques which may be of independent interest, including a new data-oblivious Euclidean primitive called hierarchical Lipschitz assignment, a robust dimensionality reduction for clustering, and a robust streaming algorithm for inner-product queries.

Thu 5 NovData Structures and Algorithms
The gist
Clustering is a way to group similar points in space, but it can be hard to do accurately when data arrives in a stream and might be influenced by tricky or changing inputs. This paper presents new algorithms that find almost the best groupings for two common types of clustering, called k-Median and k-Means, while using much less computer memory than before. The authors also introduce new tools that help reduce data complexity and keep results reliable even if the input changes in adversarial ways. These improvements make streaming clustering more practical and robust in real-world conditions.
Open → 2611.07678v1

Compact structure encodes all pairs mincuts in linear space

Beyond Gomory-Hu: All-Pairs $\times$ All-Pairs Mincuts in $O(n)$ Space

Abstract: For over four decades, two classical structures have offered complementary views of mincuts. The Gomory-Hu tree encodes one $(x,y)$-mincut for every vertex pair $x,y$ in $O(n)$ space, but retains only one mincut per pair. In contrast, for a fixed pair $x,y$, the Picard-Queyranne representation admits an $O(n)$ space vertex ordering that determines whether some $(x,y)$-mincut separates any given pair $u,v$ and reports such a cut. Can these complementary guarantees hold simultaneously in $O(n)$ space? We answer affirmatively. For undirected graphs, we construct an $O(n)$ space structure encoding, for every four vertices $x,y,u,v$, an $(x,y)$-mincut separating $u,v$ whenever one exists. More precisely, given any terminal pair $x,y$, the structure recovers the Picard-Queyranne ordering in $O(n)$ time. Thereafter, separability queries take $O(1)$ time, and reporting a separating mincut $C$ takes $O(|C|)$ time. Thus, information for all $Θ(n^4)$ choices of $x,y,u,v$ is encoded in $O(n)$ space. This is essentially the strongest information of this form that fits in $O(n)$ space: if one additionally requires the mincut to place $u$ on side of $x$ and $v$ on side of $y$, then $Ω(n^2)$ space is necessary even for fixed $x,y$. As a consequence, we obtain an $O(n)$ space all-pairs mincut sensitivity oracle for a single edge failure in multigraphs, with optimal $O(n)$ time to report a new mincut. This resolves an open question of Baswana and Pandey [SODA'22] on achieving $o(n^2)$ space and $o(m)$ query time simultaneously. Our construction substantially generalizes the $O(n)$ space nearest-mincut-hierarchy [SODA'27], which reports only the nearest $(x,y)$-mincut. Recovering the entire Picard-Queyranne ordering for an arbitrary pair requires new structural properties of the Dinitz-Vainshtein [STOC'94] connectivity carcass, extending its use beyond the Steiner mincuts it represents.

Wed 4 NovData Structures and Algorithms
The gist
Finding the smallest cuts in a network connecting different points is important but can require a lot of storage. The authors built a new way to keep track of these cuts for all pairs of points while using only space proportional to the number of points, not the number of possible pairs. This method quickly answers questions about which points a minimum cut separates and retrieves the actual cut efficiently. Their work also improves tools that quickly adapt to failures in a network by using less memory and fast response times.
Open → 2611.06478v1

Improved algorithms estimate and find matchings in bipartite graphs faster

Optimal LCA and Sublinear Estimation for Bipartite Matching in $Δ^{O(1/\varepsilon)}$ Queries

Abstract: A local computation algorithm (LCA) for matching answers ``who is the mate of $v$?'' by inspecting only a small part of the graph, with all answers consistent with one matching. For $n$-vertex graphs of maximum degree $Δ\ge2$, Levi et al. [Algorithmica'17] give a $(1-\varepsilon)$-approximate matching LCA using $(Δ/\varepsilon)^{O(1/\varepsilon^2)} \operatorname{polylog}(n)$ queries per invocation, while Yoshida et al. [SIAM J. Comput.'12] estimate the maximum matching size within additive error $\varepsilon n$ using $Δ^{O(1/\varepsilon^2)}$ queries. Behnezhad, Roghani, and Rubinstein [FOCS'23] proved a $Δ^{Ω(1/\varepsilon)}$ lower bound for both tasks, even on bipartite graphs and even when the LCA's matching guarantee is relaxed to additive $\varepsilon n$ error. This leaves a gap between linear and quadratic dependence on $1/\varepsilon$ in the exponent. We close this gap on bipartite graphs. We give an LCA that answers each mate query with $Δ^{O(1/\varepsilon)}$ queries for a $(1-\varepsilon)$-approximate matching, and an estimator for the maximum matching size within $\varepsilon n$ using $Δ^{O(1/\varepsilon)}$ queries. On general graphs, the same algorithm gives a half-integral fractional matching and estimates the maximum fractional matching size. Our approach runs $O(\varepsilon^{-1}\logΔ)$ rounds of a deterministic local optimization method in which vertices propose to neighbors and update prices according to incoming loads. We design its updates to admit exact recursive sampling with constant expected branching, obtaining the improved randomized bound without exploring full dependency neighborhoods. To our knowledge, this is the first LCA construction based on exact recursive sampling of the iterates of a deterministic continuous optimization method. We expect this approach to have applications beyond matching.

Wed 4 NovData Structures and Algorithms
The gist
Finding pairs in a network, like matching people or jobs, can be tricky when you want to do it quickly without looking at the whole network. The authors improved algorithms that answer matching queries by looking at only a small part of the network, especially for bipartite graphs. Their method uses fewer steps than before while still giving almost the best possible matches or estimates of the maximum matchings. They do this by cleverly combining a deterministic process with a sampling technique that avoids checking too many connections at once.
Open → 2611.06024v1

Parallel sorting algorithms run faster across multiple computing models

Sorting in PRAM, Parallel Comparison Model and Parallel External Memory Model

Abstract: We study the problem of sorting on the Parallel Random Access Machine (PRAM), Parallel Comparison Model (PCM) and Parallel External Memory Model (PEM). On PRAM, we present a Concurrent Read Exclusive Write algorithm that runs in $O(\log n)$ time with $n$ processors; our algorithm is very different from Cole's Merge Sort. On PCM, we present the first optimal algorithm for sorting after AKS; our algorithm runs in $O(\log n/\logα)$ comparison rounds with $nα$ processors, for $1\leqα\leq n$. On PEM, we present a Concurrent Read Exclusive Write algorithm that sorts $N$ elements in $O\left(\log\frac{N}{B}\right)$ I/O rounds with $p\geq \frac{N}{B}$ processors.

Tue 3 NovData Structures and Algorithms
The gist
Sorting large amounts of data quickly is important for many computer programs. This paper shows new ways to sort data faster using many processors working in parallel. The authors provide improved methods for three different computer models, each suited for different hardware setups. Their new algorithms reduce the time it takes to sort by cleverly coordinating many processors without conflicts. These improvements could speed up data processing in systems with multiple processors or external memory.
Open → 2611.04914v1

Directed graph tree covers improve distances routing and spanners

Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners

Abstract: In a seminal work [STOC'01; JACM'05], Thorup and Zwick showed that every weighted undirected graph admits a tree cover where each vertex belongs to $O(kn^{1/k})$ trees in expectation, and every pair has a path of stretch at most $2k-1$ in some tree. In this paper, we extend this structural property to directed graphs with nonnegative edge weights. Let $\mathrm{dist}_G(u \leftrightarrows v) = \mathrm{dist}_G(u \to v) + \mathrm{dist}_G(v \to u)$ denote the roundtrip distance. For every integer $k$, we construct a collection $\mathcal{T}$ of tree-pairs, each consisting of an in-tree and an out-tree rooted at the same vertex. Each vertex belongs to $O(kn^{1/k})$ tree-pairs in expectation, and for every ordered pair $(u, v)$ some tree-pair $T_{in}\cup T_{out} \in \mathcal{T}$ satisfies $\mathrm{dist}_{T_{in}\cup T_{out}}(u \to v) \le \mathrm{dist}_G(u \to v) + (k-1)\mathrm{dist}_G(u \leftrightarrows v).$ We call this a \emph{$k$-strong (roundtrip) tree cover}. While prior techniques partition distances into geometric scales and build separate structures for each scale, our construction handles all distances simultaneously within a single, unified hierarchy. This yields the first directed tree cover for general $k$ matching the classic Thorup-Zwick stretch-size trade-off. Our cover immediately implies improved constructions of roundtrip spanners, path-reporting distance oracles, and compact routing schemes, as well as their source-wise and prioritized variants. We also provide faster algorithms for these structures: for general $k \ge 4$, all the above objects can be constructed in $\widetilde{O}(\min\{mn, n^{2.5}\})$ expected time, breaking the $mn$ barrier in dense directed graphs.

Tue 3 NovData Structures and Algorithms
The gist
Measuring distances and finding good routes in one-way networks (directed graphs) is tricky because paths may not easily reverse. The authors extended a famous method that worked well for two-way networks to these one-way cases. They built a set of special tree structures that cover the network and help approximate the shortest paths with limited extra distance. This helps create faster tools for answering distance questions, routing data, and simplifying the network, with strong efficiency even for large networks.
Open → 2611.04731v1

Space efficient method speeds graph cut approximation in data streams

Near-Optimal Space and Time Cut Sparsification in Turnstile Streams

Abstract: A seminal result of Ahn, Guha, and McGregor (PODS'12) showed that a cut sparsifier of an unweighted graph can be computed from a near-linear number of linear measurements. Later work extended this to spectral sparsifiers (Kapralov et al., FOCS'14) and to near-linear recovery time (Kapralov et al., SODA'20). For weighted graphs, these sketches rely on grouping edges by weight, which general turnstile streams do not allow. Chen, Khanna, and Li (FOCS'22) removed this limitation, using $\tilde{O}(n/\varepsilon^3)$ bits of space. We improve the space to $\tilde{O}(n/\varepsilon^2)$ bits. Our algorithm makes one pass over a general turnstile stream of a weighted graph, processes each update in $\tilde{O}(1)$ time, and recovers, in $\tilde{O}(n/\varepsilon^2)$ time, a reweighted subgraph with $O(n\varepsilon^{-2}\log^2 n)$ edges that preserves every cut within a factor of $1\pm\varepsilon$. Its space, update time, and recovery time are all optimal up to polylogarithmic factors.

Mon 2 NovData Structures and Algorithms
The gist
Graphs can be very large and hard to store or process entirely, so it's useful to create smaller versions that still keep key features like how cuts divide the graph. The authors improved a method that reads updates about a weighted graph one by one in a stream and builds a smaller graph preserving all cuts approximately. Their approach uses less memory and runs faster than previous ones while maintaining accuracy. This helps when dealing with big, changing graphs like social networks or traffic systems.
Open → 2611.03604v1

RegionFence speeds up blockchain transaction processing by nine times

RegionFence: Adaptive Concurrency Control for Blockchain Parallel Transaction Execution

Abstract: Smart contracts have turned blockchains into general platforms, and their throughput is increasingly limited by transaction execution. Parallel execution can relieve this bottleneck. However, most existing engines apply a single policy within a block, typically optimistic (OCC) or pessimistic (PCC) concurrency control, and thus re-execute or delay whole transactions. Although some database studies have proposed hybrid and adaptive mechanisms, these mechanisms cannot be applied directly to blockchains because the block fixes the serial order, accesses emerge only at run time, and real workloads vary widely. We propose RegionFence, an adaptive concurrency control mechanism for blockchain parallel transaction execution, based on three key designs. First, we propose regions to refine the granularity of control from whole transactions to the parts that touch contended keys. Second, we design fences to decide at run time how each region handles a conflict. Third, we introduce intra-block and inter-block online learning to anticipate likely conflicts. At the same time, the system still produces the same result as serial execution in consensus order. We implement RegionFence in go-ethereum and evaluate it on real Ethereum mainnet blocks from different periods of the past five years. Experimental results show that RegionFence achieves an overall speedup of 9.2x over single-core execution on 64 cores and outperforms OCC by 2.9-5.4x and PCC by 3.9-9.4x in speedup across these periods.

Sun 1 NovDistributed, Parallel, and Cluster Computing
The gist
Blockchain systems slow down when many transactions try to run at the same time because they need to be careful not to mess up the order of events. The authors present RegionFence, a method that divides transactions into smaller parts called regions and smartly decides how to handle conflicts as they happen, using learning to predict problems. This lets many parts of transactions run at the same time safely, making blockchain operations faster without changing the final results. They tested RegionFence on real Ethereum data and found it works much faster than existing methods.
Open → 2611.02164v1

Faster approximate matching algorithms for large dynamic graphs

Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework

Abstract: We study the $(1-\varepsilon)$-approximate maximum weight matching problem in general graphs with $n$ vertices and integer edge weights in $[1,W]$. For $W=n^{O(1)}$, we obtain faster algorithms in the semi-streaming and dynamic settings: (1) Semi-streaming: Deterministic $O(\varepsilon^{-2})$-pass and $O(\varepsilon^{-2}\log(1/\varepsilon))$-pass algorithms for unweighted and weighted matching. (2) Incremental: A deterministic algorithm for weighted matching processing $m$ edge insertions in total time $O((m\varepsilon^{-3}+n\varepsilon^{-6})\log^3 n)$. (3) Decremental: A randomized algorithm for weighted matching processing all edge deletions from an $m$-edge graph in total time $O((m\varepsilon^{-8}+n\varepsilon^{-47})\log^{O(1)}n)$ with high probability. (4) Fully dynamic: A deterministic reduction from weighted matching in general graphs to unweighted matching in bipartite graphs incurring $O(\varepsilon^{-4}\log^{O(1)}(1/\varepsilon))$ multiplicative update-time overhead, independent of $n$. Underlying these results is a unified framework that reduces the problem to repeatedly solving two simpler matching subproblems: a $(1-\varepsilon)$-approximate maximum weight matching on a sparse subgraph with $O(n/\varepsilon)$ edges, and a constant approximation on the remaining edges. The framework builds on dual entropy regularization, a smoothing technique underlying efficient solvers for packing linear programs. To handle the exponentially many odd-set constraints, we adapt the smoothing technique to regularize only the vertex duals and develop a new cut partition that preserves odd-set feasibility during optimization.

Sun 1 NovData Structures and Algorithms
The gist
Finding the largest possible set of matched edges in a network is an important problem in computer science. This paper presents faster algorithms to find approximate solutions for weighted matchings in large graphs, even when the graph changes over time by adding or removing edges. The authors introduce a unified approach that breaks down the problem into easier parts and uses a smoothing technique to handle complex constraints efficiently. Their methods work well in streaming data and dynamic graph updates, improving speed while maintaining good approximation quality.
Open → 2611.02105v1

Order-invariant cluster logic includes local-order-invariant logic on finite structures

Order-Invariant CFO Contains Local-Order-Invariant FO

Abstract: Order-invariant cluster first-order logic (CFO) and local-order-invariant first-order logic are two fragments of order-invariant first-order logic, both motivated by the study of invariant logics on classes of bounded degree. Our main result is that order-invariant CFO contains local-order-invariant FO on arbitrary classes of finite structures, settling the conjecture of Ghasemi and Grange that order-invariant CFO contains plain FO. By combining this with a collapse result of Ghasemi and Grange, we obtain the equivalence of FO, local-order-invariant FO, and order-invariant CFO on classes of finite colored graphs of bounded degree. The proof makes use of Gaifman normal form, which allows our translation from local-order-invariant FO to order-invariant CFO to be effective. Combined with the fixed-parameter tractability of model-checking for order-invariant CFO on bounded-degree colored graph classes, this shows that model-checking for local-order-invariant FO on bounded-degree colored graph classes is fixed-parameter tractable. To generalize our collapse and model-checking results beyond colored graphs, we use a method based on first-order interpretations which also yields a collapse of order-invariant FO to FO when restricted to graph classes of bounded shrub-depth. Finally, we give an application to the database-motivated frozen-witness logic of Abiteboul, Simon, and Vianu by showing that local-order-invariant FO contains deterministic frozen-witness FO, and thus that deterministic frozen-witness FO collapses to FO on classes of finite structures of bounded degree.

Sun 1 NovLogic in Computer Science
The gist
The paper studies different ways of writing logical statements that are unaffected by how elements are ordered in a structure, focusing on certain technical subsets of these logics. It shows that one such logic called order-invariant cluster first-order logic (CFO) is powerful enough to express everything that the local-order-invariant first-order logic can on any finite structure. This settles a previous question about their relative expressiveness. The authors also show that these logics behave the same on graphs with limited connections per node, and that checking statements in these logics can be done efficiently in such cases.
Open → 2611.01501v1

Adaptive scheduling improves performance of sparse matrix multiplication

Taming Multi-Dimensional Skew in Sparse Matrix Multiplication with Contention-Aware Scheduling [Technical Report]

Abstract: Sparse general matrix-matrix multiplication (SpGEMM) is a key kernel in graph analytics, relational queries, and machine learning. Yet, its performance remains a significant challenge, due to the inherent sparsity and, more critically, the prevalent skew patterns often found in real-world workloads. This paper investigates this problem and demonstrates that an unbalanced workload distribution is the main culprit, harming performance through two co-existing root causes: first, multi-dimensional skew, where imbalance across computation cost, output density, and data locality cannot be captured by any single balancing metric; and second, cache contention, where dense substructures induce severe on-chip interference. To that end, we propose adaptive morsel scheduling (AMS), a dynamic scheduling framework that decouples skew dimensions via fixed-result-size morsels and integrates contention-aware load balancing (CALB) and data-conscious simultaneous multithreading activator (SMTact) to alleviate cache-level contention, alongside a hybrid accumulation mechanism (HYB) that adaptively selects the best accumulator per morsel. Evaluations across matrix squaring, relational queries, graph analytics, and other sparse matrix kernels show that AMS significantly outperforms state-of-the-art methods on skewed workloads while maintaining comparable performance on non-skewed ones. These gains, along with improved bandwidth utilization, remain valid across a wide range of workloads and hardware systems.

Tue 27 OctDistributed, Parallel, and Cluster ComputingDatabases
The gist
Sparse matrix multiplication is important for many technologies like graph analysis and machine learning but can run slowly because the work isn't evenly spread out. The authors found that the problem comes from uneven workload distribution and interference in the computer’s memory cache. They created a new method called adaptive morsel scheduling (AMS) that splits work carefully and manages memory better. This approach runs faster than current methods on tricky, unbalanced tasks and works well on regular ones too.
Open → 2610.36822v1

Efficient algorithms improve selecting ordered elements under partial information

Selection under partial information

Abstract: The selection problem asks to find the $k$-th smallest element in a given set $X$. Its complexity is well-known to be $Θ(|X|)$ for every fixed $k$. We consider the poset selection problem where a partial order $P$ on $X$ is given, and the underlying order of $X$ is guaranteed to be a linear extension of $P$. This generalizes several variants of the selection problem studied before. Our main result is an algorithm that performs $O( k + \operatorname{OPT}(P,k) )$ comparisons, where $\operatorname{OPT}(P,k)$ is the minimum number of comparisons required for the input $(P,k)$. If $P$ is a rooted tree, we obtain an $O( \operatorname{OPT} \log (k / \operatorname{OPT}) )$ algorithm, which can be further improved to $O( \operatorname{OPT} \log \log (k/\operatorname{OPT}) )$ or $O( \operatorname{OPT} \log \operatorname{OPT})$ under mild assumptions about $P$. Our algorithms are based on the work of Kaplan, Kozma, Zamir, and Zwick [SOSA 2019], who used Chazelle's soft heaps [J. ACM 2000] to simplify several older results. We introduce a new soft heap variant, the weighted soft heap, which allows greater control over which elements get corrupted.

Fri 23 OctData Structures and Algorithms
The gist
Selecting the k-th smallest item in a list is well-understood when all elements can be compared. This paper studies the problem when only some comparisons are known in advance, given as a partial order, and the full order must agree with it. The authors develop algorithms that adapt to this partial order and use fewer comparisons than before, especially when the partial order has special structures like trees. They also create a new variant of a data structure called a soft heap, helping control which data becomes uncertain during the algorithm.
Open → 2610.32731v1

Deterministic incremental triconnectivity updates in logarithmic time

Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time

Abstract: We consider the problem of maintaining the triconnectivity in some biconnected graph G in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries of the form "are there at least three vertex disjoint paths between a and b?". All algorithms presented in this paper are deterministic. All queries and updates are answered in worst-case $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get an algorithm for general graphs with a worst-case running time of $O(\log^2 n)$ per operation. These algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.

Fri 23 OctData Structures and Algorithms
The gist
This paper deals with how to efficiently keep track of strong connections in a network as it grows. The authors focus on triconnectivity, meaning there are at least three separate ways to get from one point to another. They present algorithms that can update and answer queries about these connections quickly and predictably every time the network changes. Their method improves the speed of previous solutions, making it faster to maintain such connectivity information in dynamic networks.
Open → 2610.32721v1

Speedrun leaderboard speeds up relational transformer training times

Speedrunning Relational Foundation Model Pretraining

Abstract: Progress on foundation model pretraining is gated by who can afford a trial, and relational pretraining is no exception. Recipes are developed inside individual labs, reported under private protocols, and do not accumulate. Speedrun leaderboards remove that barrier by decentralizing the search rather than the training run. The problem is fixed, the stack is open, entries are ranked by wall-clock time to a quality target, and one GPU is enough to hold the record. We introduce modded-nanoRT, the first such leaderboard for Relational Transformers. Which database to hold out decides whether the benchmark can resolve improvements at all, so we fix it by calibration, ranking six candidates by how sharply a 45-minute learning curve separates improvement from seed noise. We open the leaderboard with typed trilinear attention, a relational operator that conditions attention scores and values on the foreign key traversed, together with Muon and SIGReg. The recipe reaches the target in 305.63 seconds on one NVIDIA H200, 8.11x faster than the reference implementation, and wins 13 of 15 pairs outside the development database. We will release the benchmark, its frozen artifacts, and the record runs. Our code is available at https://github.com/kunumi/nanoRT.

Tue 20 OctArtificial Intelligence
The gist
Training large models that understand relationships between data points can be very expensive and private, limiting progress. The authors introduce a public leaderboard called modded-nanoRT that ranks attempts by how fast they reach a certain quality using only one GPU. They develop a new method using 'typed trilinear attention' which trains relational transformers much faster than previous versions. This approach makes it easier for anyone to try improving relational model training speed and share results openly.
Open → 2610.28855v1

Space complexity advances for reachability in simple path directed graphs

Space Complexity of Reachability in Simple Path Graphs

Abstract: One of the central questions in space complexity is whether nondeterministic logspace computations ($\textsf{NL}$) can be simulated in unambiguous logspace ($\textsf{UL}$). A stronger notion, \emph{reach unambiguity} ($\textsf{RUL} \subseteq \textsf{UL} \cap \textsf{co}\textsf{UL}$), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph reachability is $\textsf{NL}$-complete, planar graph reachability is in $\textsf{UL}$ and undirected graph reachability is in deterministic logspace ($\textsf{L}$). In this work, we study the space complexity of reachability problem for restricted directed graph families and show the following. - For reach unambiguous graphs (graphs with at most one path from start vertex to every vertex), Lange (Lange 97) showed that reachability is in $\textsf{RUL}$. As our main result, we show that for simple path graphs (introduced in Kannan et.al. 08), which contains reach unambiguous graphs), where each vertex has at most one simple path from the start, we show that the reachability problem lies in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. - Our first result can also be equivalently stated as: the recognition problem for simple path is in $\textsf{UL} \cap \textsf{co}\textsf{UL}$ if and only if the reachability problem restricted to simple path graphs is also in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. Inspired by this, we investigate the complexity of graph recognition versus graph reachability for graph classes. Observe that for any graph class, solving reachability (for the class) also solves the recognition problem for that class. We show that for reach unambiguous graphs, solving recognition is as hard as solving reachability (making both of them $\textsf{RUL}$-complete). (Abstract shortened to meet arXiv limits)

Tue 20 OctComputational Complexity
The gist
This paper looks at a problem called the reachability problem in computer science, which is about checking if there is a path from one point to another in a network. The researchers studied special types of networks called simple path graphs, where each point can be reached by only one unique route. They showed that deciding if a point is reachable can be done using very little memory, improving on previous knowledge about related graphs. They also connected this problem with figuring out whether a network itself fits into this special category.
Open → 2610.27879v1

New space efficient method for streaming graph coloring decisions

Improved Space Bounds for Promise Graph Coloring in Adversarial Streams

Abstract: We study promise graph coloring in one pass insertion-only adversarial streams. We give a randomized algorithm that distinguishes 3-colorable graphs from graphs that are not 6-colorable using $O(n^{3/2}\log(n/\varepsilon)\log n)$ bits of space. This provides a truly subquadratic space algorithm for a constant coloring gap, answering an open problem posed by Assadi, Sundaresan, and Yazdanyar [SODA 2026] for $q=3$. Combining this algorithm with the vertex-sampling lemma of Assadi et al.\ yields, for any $144\lceil\log_2 n\rceil\le Q\le n$, a one-pass decision algorithm distinguishing $3$-colorable graphs from graphs that are not $Q$-colorable using $O((n/Q)^{3/2}\log^5 n)$ bits of space. This improves upon the $\widetilde{O}((n/Q)^2)$ bound achievable via dynamic streaming techniques. Setting $Q=\lceil n^{1/3}\rceil$ yields a semi-streaming decision algorithm, answering the decision version of another open problem posed by Assadi et al. On the negative side, we prove that distinguishing $χ(G)\le q$ from $χ(G)\ge(q-1)^2$ requires $Ω(n^2/q^5)$ bits of space, improving upon the previously established $q^2/4$ threshold using the same space complexity.

Sat 17 OctData Structures and AlgorithmsComputational Complexity
The gist
Choosing colors for a network's points without using many computers’ memory is tough, especially when the data arrives all at once and can be tricky. The authors found a way to use less memory to tell if a network can be colored with 3 or more colors in a single pass. They improved older methods and also showed limits on how little memory can be used for certain coloring problems. This helps solve some open questions about graph coloring in data streams.
Open → 2610.24644v1

Faster way to compute shortest paths in big networks

Simple, Faster (min, +) Matrix Multiplication and APSP

Abstract: In this note, we provide a deterministic algorithm that computes the $(\min, +)$-Matrix Product $C = A * B$ of two $N \times N$ matrices $A$ and $B$ with polynomially bounded integer entries in $\tilde{O}(N^{2.9964})$ time, improving upon the exponent of $O(N^{2.9995})$ time obtained in the recent breakthrough by Anthropic (Alman and Vassilevska Williams, 2026). Our algorithm uses a phased approach first proposed by Bringmann, Grandoni, Saha, and Vassilevska Williams in 2016. The phased approach produces an approximation $\tilde{C}$ of $C$ in truly subcubic time such that the number of remaining triples $(i,k,j): A_{i,k}+B_{k,j} < \tilde{C}(i,j)$ is truly subcubic. This provided strong evidence that a truly subcubic $(\min, +)$-Matrix Product and therefore, a truly subcubic algorithm for All Pairs Shortest Paths (APSP) may exist. However, to find the remaining triples in subcubic time, a sparse certificate is needed whose construction was not known. We use the thin matrix product theorem of the recent breakthrough to provide such a certificate. This gives a simple modular subcubic algorithm for APSP.

Wed 14 OctData Structures and Algorithms
The gist
Finding the shortest routes between all points in a large network is a key problem in computing. The authors improved the time needed to do this calculation using a new method that breaks the problem into phases. Their approach finds an approximate solution quickly and then efficiently fixes the remaining errors using a new mathematical tool. This leads to a faster algorithm for computing shortest paths between all pairs of nodes in a network.
Open → 2610.20297v1

Network coding enables faster external-memory integer sorting algorithms

Undirected Network Coding and Faster External-Memory Integer Sorting

Abstract: Network coding allows intermediate nodes to combine messages, whereas routing only forwards them. The Li-Li conjecture asserts that network coding and fractional routing have the same capacity region in undirected multiple-unicast networks. We give a counterexample to this conjecture and apply it to external-memory integer sorting. Since Aggarwal and Vitter posed the question in 1988, whether integer sorting can beat the external-memory comparison bound has remained a central and extensively studied open problem. We give a deterministic sorting algorithm: for $N$ integers of $Θ(\log N)$ bits, a memory holding $M$ integers, and block transfers of $B$ integers, where $2B\le M\le N$, the number of block transfers is $O\left(\frac{N}{B}\left[1+\frac{\log N}{(\log(M/B))^{1-\varepsilon}(\log M)^\varepsilon}\right]\right)$, where $\varepsilon>0$ is an absolute constant. In a range of parameter regimes, this bound is asymptotically smaller than the classical comparison-sorting bound. We also use Lean 4 to verify the sorting algorithm's correctness and complexity bounds, and the strict advantage of coding over routing.

Wed 14 OctData Structures and AlgorithmsComputational ComplexityInformation Theory
The gist
The paper tackles the problem of sorting large lists of numbers stored mostly on slow external memory like hard drives. Normally, sorting is limited by how often data must be moved in and out of memory. The authors show a new way to combine messages during data transfer that breaks this limit, making sorting faster in some cases. They also prove that combining messages (network coding) can be more powerful than just forwarding data (routing) in certain network setups. To ensure their method is correct, they used a formal verification tool called Lean 4.
Open → 2610.20079v1

Coral speeds up and improves cross modal vector search at scale

CORAL: Cross-modal Vector Retrieval via Incremental Graph Construction at Scale

Abstract: Cross-modal vector retrieval is widely used in multimodal systems, such as search engines and vector databases. It typically operates in out-of-distribution (OOD) settings, where query vectors follow a distribution that differs from that of the vectors stored in the database. In such cases, conventional indexes suffer significant performance degradation, and even methods specially designed for OOD remain limited by inefficient use of query modal characteristics, restricted GPU parallelism, and inadequate support for dynamic updates. We present CORAL, a novel GPU-accelerated graph-based vector index for scalable cross-modal retrieval, featuring hierarchical memory management that spans GPU, CPU, and disk. Specifically, CORAL incrementally incorporates the characteristics of query modality and terminates index construction timely. Crucially, it introduces coverage-aware adaptive pruning to address the imbalanced coverage of the query vector's neighbors. Moreover, CORAL presents a fully neighborhood-aware projection approach to efficiently utilize GPUs for highly parallel index construction, and a targeted connectivity enhancement method to refine the index structure. Besides, CORAL also supports modal-semantics-based vector insertion and topology-repairing deletion that restore node connectivity. Experimental results demonstrate that CORAL outperforms existing methods with up to 1.6 times the throughput at matched recall while reducing construction time by up to 56%. Furthermore, it exhibits remarkable resilience under dynamic updates and remains effective at the billion scale.

Thu 8 OctDatabases
The gist
Cross-modal vector search helps match data from different types, like images and text, but it often struggles when the queries look very different from the stored data. The authors introduced CORAL, a new system that builds a graph-like structure to organize data vectors and uses GPUs efficiently to handle huge amounts of information. CORAL also updates this structure dynamically, so it stays accurate as new data comes in or old data is removed. Their tests show it works faster and better than previous methods, even for very large datasets.
Open → 2610.11230v1

Fast algorithm improves solving maltsev constraint problems

A Fast Algorithm for Maltsev Constraints

Abstract: The constraint satisfaction problem over a set of relations $Γ$ (CSP($Γ$)) is the computational problem of deciding if a set of constraints admits at least one solution. The classical complexity for finite-domain CSP($Γ$) is settled by the CSP dichotomy theorem: it is tractable if $Γ$ satisfies a non-trivial algebraic invariant and is NP-complete otherwise. However, not all these algebraic invariants result in efficient algorithms despite being theoretically tractable. A notable case that generalizes linear equations is that of Maltsev CSPs: an $n$-variable instance with $m$ constraints is solvable in roughly $O(n^8 \cdot m)$ time by Bulatov and Dalmau (SIAM J. Comput. 2006) or $O(n^4 \cdot m)$ time by Dyer and Richerby (SIAM J. Comput. 2013). At the same time, arguably, most "natural" and efficiently usable polynomial-time algorithms rarely exceed a quadratic or cubic time bound. In this paper we revisit Maltsev constraints with this question in mind and find a $O(n^2 \cdot m)$ algorithm (for finite languages, for infinite languages we in addition need to take the total size of the instance into account). The main novel idea is to not attempt to improve the bottleneck in Bulatov and Dalmau (the Fix-Values procedure) but to avoid it altogether with a slightly more refined approach that allows us to search through a smaller space.

Tue 6 OctComputational ComplexityData Structures and Algorithms
The gist
Constraint satisfaction problems ask if there's a way to assign values to variables so all rules hold true. Some special types, called Maltsev constraints, are linked to algebra and can be solved efficiently but still take a long time with existing methods. The authors found a new algorithm that solves these problems much faster by avoiding a usual slow step and exploring fewer possibilities. This makes it quicker to handle these constraints in practice.
Open → 2610.08207v1

Models learn relations when data forces cross-table predictions

When Does Synthetic Relational Data Teach Models to Use Relations? Tracing Predictive Structure from Pretraining Data to Model Behavior

Abstract: Relational foundation models are increasingly pretrained on synthetic databases, yet downstream benchmarks reveal little about why one synthetic corpus produces a better model than another. In particular, strong performance may arise from realistic row-level statistics without the model ever learning to use relational structure. We study this as a data-attribution problem: which property of synthetic pretraining data induces relational computation? Using four Relational Transformer checkpoints trained with the same architecture, initialization, objective, and compute budget on corpora produced by four relational data generators, we trace a measurable property of the data to learned computation and downstream behavior. We hypothesize that relational mechanisms emerge when cross-table information is predictively necessary for the masked-cell pretraining objective. RelDiff exhibits by far the largest predictive gain from foreign-key-linked parents, and its corresponding model is uniquely sensitive to foreign-key interventions on unseen databases. This dependence survives a random-initialization control, grows monotonically with the fraction of corrupted links, and localizes to a serial cross-table pathway. Finally, disrupting the same mechanism during downstream inference removes RelDiff's advantage on relational tasks while leaving structure-insensitive models nearly unchanged. These results connect a property of synthetic training data to a learned mechanism and, through intervention, to downstream behavior.

Fri 2 OctMachine Learning
The gist
The paper looks at how artificial databases help AI models learn to use relationships between tables. The researchers found that models only develop the ability to link information across tables if the training data actually requires this to succeed. They traced this effect by comparing models trained on different types of synthetic data and showed that certain data properties make models rely on relational connections. When those connections are broken during testing, only the models trained on the right data lose performance on relational tasks. This shows which data properties teach models to handle relations.
Open → 2610.03057v1

Text to SQL model accuracy improves using plans across database dialects

Closing the Cross-Dialect Gap: Query Plans as a Portable Interface in Text-to-SQL

Abstract: Text-to-SQL systems are typically trained and evaluated on a single dialect (SQLite), yet production deployments span PostgreSQL, MySQL, ClickHouse, and beyond. We show that this single-dialect assumption leads to a substantial drop in cross-dialect accuracy for every model we tested. The drop persists across scale, architecture, and even purpose-built text-to-SQL systems. We argue that the fix is to change the generation target: instead of asking an LLM to emit dialect-specific SQL, we have it emit a dialect-agnostic relational algebra query plan, which a deterministic compiler then renders into SQL for any supported backend. Across thirteen models from 3B to frontier scale, this restores cross-dialect portability nearly uniformly, at a small cost in peak accuracy on the model's home dialect for capable prompted models and none once fine-tuned on plans; under matched fine-tuning, plan supervision yields a stronger model than SQL supervision. We also introduce MetricName, a question-aware result-set comparator needed to evaluate fairly across dialects, where existing metrics confound semantic errors with benign cross-dialect variation. More broadly, the result is a reminder that a generation target chosen for execution is not necessarily the one that maximizes generation quality.

Sun 27 SeptComputation and Language
The gist
Text-to-SQL models usually learn one type of database language, which causes errors when used with others. The authors show this is a big problem for many models. They suggest having the model produce a general query plan, which can be turned into any specific database language afterwards. This method improves accuracy across many SQL languages without hurting performance on the original language, and sometimes even improves it. They also created a new way to fairly measure correctness across different database languages.
Open → 2609.33670v1

Transformer memory restructured to enable exact reuse and deletion

Memory as a cache: Exact context reuse and deletion by construction

Abstract: The KV cache of a transformer entangles every token's representation with its entire prefix: a passage encoded once cannot be reused under a different prefix or removed without recomputing everything after it, so exact cache reuse is limited to shared prefixes. We present SMem, an architecture whose context representation is a cache by construction. A block-local encoder maps each block to memory rows independently of other blocks, and a reader conditions generation on their union through cross-attention. For every parameter setting, memory composes exactly at fixed block indices, deleting a block is an exact $O(b)$ update for $b$-token blocks, and the memory state is independent of the edit path. At $4\times$ the training context, under the shared recipe, SMem retrieves planted needles beyond any trained-length window (exact match 0.14-0.28 at distances of 31 and 63 blocks), where learned-position, RoPE, and Block-Attention-style transformers all score at most 0.02. A fully cached context is served by computing one block alone at a near-constant 3.1-6.2 ms, whereas cold prefill grows with context; batched decode stores 34-38% fewer KV rows and runs 1.4-1.7$\times$ faster when bandwidth-bound; and deletion beats suffix recomputation by 8.5$\times$ at 512 blocks and 452$\times$ at 4096 blocks (32-256$\times$ the trained length, probing the cost model rather than a served regime). The cost is a perplexity gap of -4.7% to +2.8% (negative favors SMem) against a parameter-matched transformer with the same positional scheme, at 160M-1.5B on FineWeb-Edu across two recipes and a learning-rate search. SMem also composes with RoPE: at 160M and 410M the composite matches or leads the matched transformer and closes 29-59% of SMem's gap to a RoPE transformer. Dropping prefix entanglement thus keeps perplexity comparable while making the cache exactly composable and editable.

Sat 26 SeptArtificial IntelligenceMachine Learning
The gist
Current transformer models combine every token’s memory with everything before it, making it hard to reuse parts or remove sections without recalculating everything after. The authors introduce SMem, which stores memory in separate blocks that can be combined exactly and updated efficiently. This allows removing or reusing parts of the memory quickly without affecting the rest, and keeps prediction quality close to standard models. SMem also works well with common positional encoding methods to maintain accuracy.
Open → 2609.32395v1

Deciding bag query containment using controlled Diophantine equations

Attacking Diophantus: Special Cases of Bag Containment

Abstract: Query containment is a fundamental decision problem in database theory: given two queries, determine whether, over all database instances, every answer produced by the first is also produced by the second. For conjunctive queries under set semantics, the problem is understood through the classical homomorphism-based characterisation. Under bag semantics, the interpretation underlying real relational databases, containment becomes a quantitative comparison of answer multiplicities. Despite decades of work, the decidability of bag containment for conjunctive queries remains open. This frontier is fragile: for slightly more expressive classes, bag containment is undecidable, with negative results relying on reductions from variants of Hilbert's 10th problem. This work develops a unified framework for bag containment of conjunctive queries that subsumes two previously studied decidable cases: projection-free and join-on-free containee queries. The framework yields decidability for a broader class, called join-uniform queries, while leaving the containing query arbitrary. This contrasts with techniques that impose restrictions on the containing query. The approach identifies tractable classes based on the internal unification structure of the query whose multiplicities must be bounded. Specifically, it reduces containment to a controlled Diophantine problem. Starting from the containee query, one builds a canonical model generated by all its possible unifications, over which multiplicities admit a finite arithmetic characterisation. Containment is proved equivalent to the non-existence of solutions of a corresponding Diophantine inequality system. Although these problems are undecidable in general, we show that the systems arising from join-uniform containment form a decidable subclass. Thus, the standard source of undecidability for bag containment becomes the core of the decision procedure.

Fri 25 SeptDatabases
The gist
Checking if one database query always gives answers contained within another is a key problem in databases. When counting duplicate answers (bag semantics), deciding this containment can be very hard or impossible for complex queries. The authors create a new way to handle certain queries, called join-uniform queries, by translating the problem into a special kind of math problem with equations. They prove that for these queries, deciding containment is indeed doable, improving on earlier restricted cases. This work links tricky database questions to classic math problems about numbers.
Open → 2609.30956v1

Scan-resistant cache gadgets improve storage performance and reliability

SR-Gadgets: Make Scan-Resistant Caching Practical

Abstract: Block caches commonly serve scan-heavy I/O workloads, motivating extensive studies on scan-resistant eviction algorithms. Many of these algorithms adopt a multi-queue structure. However, they focus primarily on one-time scans and do not handle repeated scans well. Two important challenges from repeated scans are miss-ratio cliffs, where a small increase in cache size sharply reduces the miss ratio, and Belady's anomalies, where increasing the cache size increases the miss ratio. In this paper, we first develop two quantitative metrics to measure these behaviors. With these metrics, we find that LIRS is the only multi-queue algorithm that is scan-resistant (almost cliff- and anomaly-free). Contrary to conventional wisdom, we show that stack distance is not the secret sauce that makes LIRS scan-resistant. Instead, regulating the queues are the key to its scan resistance. Based on these insights, we design the \gadgetprefix Gadgets, easy-to-integrate augmentations that make existing algorithms scan-resistant without changing their eviction heuristics or queue structures. We implement the \gadgetprefix Gadgets in five algorithms: S3-FIFO, SIEVE, ARC, 2Q, and TinyLFU, and make them scan-resistant. Evaluated on 5,538 production traces, all augmented algorithms outperform their base versions, reducing miss ratios by up to 23.1% while consistently reducing cliffs and Belady's anomalies across the production traces.

Thu 24 SeptPerformance
The gist
Cache systems store data temporarily to speed up computers, but data 'scans' can cause sudden drops or unexpected increases in cache misses, hurting performance. The authors studied these problems and found that a popular algorithm called LIRS avoids them well—not because of earlier assumed reasons, but because it manages its data queues smartly. Using this insight, they created small add-ons called Gadgets that make other cache algorithms handle scans better without changing their core methods. Testing these Gadgets on thousands of real data traces showed they reduce missed data fetches and avoid weird caching problems.
Open → 2609.30468v1

Transposition rule approaches optimal list order in polynomial time

Transposition achieves OPT$+O(1)$ in polynomial time for IID list update

Abstract: In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$. Items will be queried in an IID manner according to some probability distribution $p$ on the items. We want to minimize the expected cost of each query. The optimal order is to place the items in decreasing order of probability $p_1 \geq p_2 \geq \cdots$ with expected cost $\mathsf{OPT} = \sum_j j p_j$, but the probability vector $p$ is generally unknown. Thus we use a self-organizing list following the transposition rule: an item is transposed 1 position forward whenever it is queried. Coester (2026) proved that, at stationarity measure for the transposition rule, the expected cost of a query is at most $\mathsf{OPT} + 1$. However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $σ$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.

Wed 23 SeptData Structures and AlgorithmsDiscrete Mathematics
The gist
When you have a list of items and want to find things quickly, the best way is to put the most popular items near the front. But if you don't know which items are popular, you can use a simple rule: whenever an item is accessed, swap it one step closer to the front. The authors show that this simple rule gets very close to the best possible ordering after a reasonable number of accesses, even starting from any order. Previous work proved the rule is nearly optimal on average, but this paper shows it works quickly.
Open → 2609.28397v1

Succinct storage methods improve search trees for complex networks

Succinct Representation of Search Trees on Trees

Abstract: A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where the reference tree is a path of totally ordered elements. In this paper, we study the problem of succinct representation of STTs. We consider two cases: (1) general search trees on trees, and (2) Steiner-closed search trees on trees [Bose et al. TALG 2023]. For both cases, we present representations that can be constructed in polynomial time and achieve optimal space up to the lower-order additive terms. We also present data structures for supporting fast traversals of both general and Steiner-closed STTs. For general STTs our data structure still takes optimal space up to lower-order additive terms.

Fri 18 SeptData Structures and Algorithms
The gist
Finding a specific point in a complicated network can be tricky and slow without the right tools. This paper looks at ways to store special search structures, called search trees on trees, in a very compact form so they take up less space. The researchers made sure these compact versions still let you search quickly, and that building them doesn’t take too long. Their methods work for both general cases and a more specialized version called Steiner-closed search trees.
Open → 2609.21236v1

Maximum strong independent sets improve hypergraph clustering methods

Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates

Abstract: We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified. A motivating example is multi-band LSH-MinHash deduplication, where each collision bucket gives local evidence, while connected-component contraction can impose spurious global equivalences. The paper develops an incidence-structural toolkit for this problem. We prove exact reductions for dominance, incidence twins, and weight-1 blocks; derive closed-form and low-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness-matching upper bound, and incidence-local complexity bounds. The results give correctness, termination, fixed-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide.

Wed 16 SeptMachine Learning
The gist
The paper looks at how to find the largest set of points in a network where each group of connected points contains at most one from the set. This problem is important when you want local information without assuming it spreads globally, like when deduplicating data from overlapping groups. The authors create tools and mathematical rules to simplify, estimate, and solve this problem with a step-by-step method that checks the quality of its solutions. They also describe when and how their method works best and provide examples to show the differences in how solutions can be certified.
Open → 2609.17951v1

Explicit construction of efficient graphs improves program discovery and data access

Explicit unbalanced 1-expanders with small degree and right size

Abstract: An explicit graph is given with left size $N$, left degree $\widetilde O(\log^2 N)$, right size $(1+o(1))K$ and $1$-expansion up to~$K$, meaning that every left subset of size $K' \le K$ has at least $K'$ neighbors. Let $\C(x)$ be the minimal length of a program that prints~$x$ (i.e., the central concept in Kolmogorov complexity). The $1$-expander is used to obtain an algorithm that on input $x$ computes in time $\poly(|x|)$ a list with $\widetilde O(|x|^3)$ programs such that at least 1 program prints $x$ and has length $\C(x) + O(1)$. This improves on the $O(|x|^{6+\eps})$ upper bound in~\cite{zim:c:shortlistshortproof} and is close to the $Ω(|x|^2)$ lower bound from~\cite[theorem 4]{bmvz:j:shortlist}. In the companion paper ``Online matching games in bipartite expanders: applications to data structures," the $1$-expander is used to obtain dynamic dictionaries in which the query operation has non-adaptive memory access.

Sun 13 SeptComputational ComplexityDiscrete Mathematics
The gist
The authors built a special type of network (called a 1-expander) that connects items on the left to items on the right with a small number of links. This network helps to quickly find short descriptions (or programs) that produce a given output, which is a key problem in understanding how complex data can be compressed and described. Their method speeds up an algorithm to list these short programs, making it more efficient than previous approaches. They also showed how this network can help create data structures that access memory predictably without changing during queries.
Open → 2609.14587v1

Computable limits show when sql queries are truly equivalent

Few Rows Tell Them Apart: Equivalence of Queries Mixing Set and Bag Semantics

Abstract: Bounded SQL equivalence checkers search for a counter-example database of bounded size, and a search that comes back empty proves nothing. We supply missing theory: computable bounds $B$ such that agreement on all databases with at most $B$ tuples per relation implies equivalence. We work in the combined-semantics framework, which captures SQL's mix of duplicate-eliminating (DISTINCT) and duplicate-preserving computation over set-valued relations. For conjunctive queries we prove a bound linear in the query size for fixed multiset width: inequivalent queries already disagree on a database with at most $2^w |Q|$ tuples, where the width $w$ counts only the columns the queries actually read, independently of the total number of multiset variables. Declared keys shrink the bound to $2^{kw} |Q|$ for the smaller key-width $kw$, acyclic foreign keys leave it unchanged, and the result extends to several classes of queries with comparisons, for which equivalence had not previously been characterized. For these fragments, bounded search becomes a terminating, complete decision procedure.

Wed 9 SeptDatabases
The gist
Figuring out if two database queries always give the same result is tricky when queries mix counting duplicates and ignoring them. The authors found exact size limits for small example databases you need to check to be sure two queries behave identically. These limits depend on how many columns the queries look at and some database rules called keys. This finding means that testing query equivalence can be automated and will always finish for important types of queries.
Open → 2609.09978v1

Approximate nearest neighbor search in very high dimensions under max distance

Approximate Nearest Neighbor in Ultra-High Dimensional $\ell_\infty$

Abstract: We study the approximate nearest neighbor problem under $\ell_\infty$ in the ultra-high dimensional setting where the dimension $d$ is significantly larger than the number of points $n$. Thus, we desire data structures with no dependence on $d$ in the query time. [Herold-Nanongkai-Spoerhase-Varma-Wu, SoCG 2025] introduce this problem and give data structures in $\ell_p$: for $p=1,2$, they give $(1+\varepsilon)$-approximation data structures with space $\tilde{O}(n\log d/\text{poly}(\varepsilon))$ and query time $\tilde{O}(n/\text{poly}(\varepsilon))$. Since any data structure must have query time $Ω(\min \{n,d\})$, this query time is nearly tight. However, their results are inefficient for $\ell_\infty$, with query time $Ω(nd)$. In order to handle the challenges of $\ell_\infty$, we introduce a notion of subset embeddings, which embed points by simply selecting a subset of dimensions. In particular, we show one may preserve all pairwise distances of an $n$ point dataset up to a factor of $O(c)$ by computing distances on only $n^{1+1/c}$ coordinates. We also show a matching lower bound: for any $c > 1$, there exists a set of $n$ points in $\mathbb{R}^{d}$ such that any subset embedding for the set with approximation $c$ must have at least $n^{1+Ω(1/c)}$ coordinates. Using our subset embeddings, we give data structures for approximate nearest neighbor in $\ell_\infty$ with space $O(n^2\log d)$, query time $\tilde{O}(n^{1+1/c})$, and approximation $O(c\log\log n)$ for any $c \geq 1$. Finally, we give another data structure for the approximate nearest neighbor under $\ell_\infty$ with the same space and query time as our subset embedding approach, but with approximation $O(c^{\log_2 3}) \approx O(c^{1.58})$. This allows us to achieve $O(1)$-approximation with query time e.g.~$n^{1.01}$

Tue 8 SeptData Structures and Algorithms
The gist
Finding the closest data points becomes tricky when you have many dimensions, especially under the max distance (ℓ∞) measure. The authors study this problem when the number of dimensions is much larger than the number of points. They develop a way to focus on only a carefully chosen subset of dimensions to speed up searches while still keeping results approximately correct. Their new methods reduce query time dramatically compared to existing solutions and allow good approximations with manageable space.
Open → 2609.09427v1

Text to sql evaluation improved with query changes and new metrics

SQLMorph: Query Mutation and Fine-Grained Metrics for Text-to-SQL Evaluation

Abstract: Text-to-SQL systems translate natural language queries into executable SQL, democratizing access to structured data. Despite recent advances driven by large language models (LLMs), evaluation remains a major bottleneck: public benchmarks fail to capture the complexity of enterprise schema, while building private evaluation sets is costly and nondeterministic, making evaluation results difficult to reproduce. To address this issue, we present SQLMorph, a framework for Text-to-SQL evaluation via query mutation. SQLMorph introduces two techniques to automatically generate and expand evaluation sets: Join Query Expansion (JQE), which systematically increases structural complexity through valid join additions, and Textual Query Augmentation (TQA), which generates controlled natural language perturbations to assess robustness to linguistic variation. JQE and TQA create targeted choke points to challenge specific system components. When applied to state-of-the-art systems, JQE increases query coverage and reveals accuracy degradation as the number of joins grows. Meanwhile, TQA shows that linguistic brittleness induced by heavy abbreviation can reduce accuracy by up to 17%. Beyond evaluation sets, SQLMorph introduces a family of execution-level metrics that address the limitations of current binary measures, such as Execution Accuracy. We define Execution Precision (EXP) and Execution Recall (EXR) to quantify the fraction of correct and recovered results, respectively, and combine them via F1 for unified scoring. Our experiments show that these relaxed metrics enable fine-grained analysis of over- and under-prediction, revealing differences across systems that binary metrics obscure. Together, SQLMorph's query mutation and fine-grained metrics support debugging and better align Text-to-SQL evaluation practices with real-world deployments.

Tue 8 SeptDatabasesArtificial Intelligence
The gist
Text-to-SQL systems help people ask computers questions about databases using everyday language. The authors found existing methods to test these systems aren’t thorough enough, especially when queries become complex or phrased differently. They created SQLMorph, which changes queries in smart ways to see how well systems handle tricky joins and varied language. They also introduced new scoring methods to better understand when parts of answers are right or wrong. This helps developers find weaknesses and improve systems for real-world use.
Open → 2609.08950v1

Streaming algorithms extend vector similarity metrics beyond equality counts

Frequency Moments Beyond Equality: Streaming Cosine Density Moments

Abstract: For a stream of nonzero vectors $x_1,\ldots,x_n\in\mathbb{R}^d$, let $u_i=x_i/\|x_i\|_2$. We define the cosine density of the $i$-th stream element by $D_i:=\sum_{j\in[n]}\langle u_i,u_j\rangle$ and study the density moments $M_p:=\sum_{i\in[n]}D_i^p$ in both the signed- and nonnegative-cosine regimes. These quantities are similarity-aware analogues of classical frequency moments: replacing cosine similarity by equality (that is, $D_i = \sum_{j\in[n]} \mathbf{1}\{u_j = u_i\}$) gives $M_p=F_{p+1}$ and, in particular, $M_{-1}=F_0$, the number of distinct elements. We give one-pass streaming algorithms and lower bounds that are tight or nearly tight in their dependence on the dimension $d$. Our results thus extend several fundamental statistics from the classical data stream literature to cosine similarity, a widely used measure for comparing vector embeddings in modern AI systems. The main challenge in proving a space lower bound for nonnegative cosine is to eliminate unwanted contributions without relying on pairs of opposite vectors. We address this through a construction that we call \emph{equal-sum moment isolation}: two insertion-only prefixes have the same cardinality and vector sum, and a finite-difference comparison cancels their common baseline while isolating the desired higher-order signal. This proof framework may be useful for other insertion-only streaming lower bounds, where direct cancellation is not possible.

Mon 7 SeptData Structures and Algorithms
The gist
When comparing many vectors, it's helpful to know how similar each one is to all the others. Previous methods focused only on counting exact matches, but this paper studies a way to measure similarity using cosine similarity, which captures angle-based closeness. The authors develop streaming algorithms that can calculate these similarity measures efficiently as new vectors arrive, using limited memory. They also prove theoretical limits on how well these calculations can be done, providing a new framework to handle challenging cases when vectors aren't just opposites.
Open → 2609.06925v1