CS Paper Radar

Optimal Convergence of Iterative Methods for Datalogo

Simon Frisk, Sungjin Im, Paraschos Koutris, Benjamin Moseley, Hung Ngo, Kirk Pruhs, Hangdong Zhao

cs.DS ·submitted 2026-10-02 21:16 UTC · v1
theory

Abstract

$\mathsf{Datalog}^\circ$ has been introduced as an extension to Datalog that increases expressiveness, yet retains simple least fixpoint semantics and admits optimization techniques such as semi-naïve evaluation and demand transformation. $\mathsf{Datalog}^\circ$ accomplishes this by generalizing the {\em or} and {\em and} operators of Datalog to addition and multiplication over a semiring. Finding a (minimal) fixpoint of a $\mathsf{Datalog}^\circ$ program is equivalent to finding a solution to a system of polynomial equations over the underlying semiring. Solving these systems of polynomial equations is not only a fundamental problem in the theory of $\mathsf{Datalog}^\circ$, but also has many applications in computer science, such as in databases, program analysis, and optimization. This paper resolves a key open problem in the theory of $\mathsf{Datalog}^\circ$: we prove a tight upper bound on the number of steps until convergence of iterative methods for solving these polynomial equation systems over a commutative $p$-stable semiring. In particular, we show that the number of steps until convergence is $O((p+1)n)$ where $n$ is the output size of the $\mathsf{Datalog}^\circ$ program. As the number of steps until convergence is only a proxy for the runtime of $\mathsf{Datalog}^\circ$ evaluation, we also consider the number of semiring operations used and show that, for a natural class of algorithms, $O((p+1)mn)$ is a tight upper bound, where $m$ is the maximum number of semiring operations per iteration.

Closest papers

Nearest neighbours by meaning across the whole index.

An Operator Approach to Register Programs for Catalytic Computing

cs.CC ·2026-09-16 ·Antoine Vinciguerra
theory similarity 0.60
Abstract

In a seminal work, Buhrman et al.\ (STOC 2014) introduced catalytic computation and proved that uniform $TC^1$ circuits are computable in catalytic logspace, the class of problems solvable in space $s$ with an additional catalytic tape of size $c$, a tape whose initial content must be restored at the end of the computation. A central ingredient of their proof is the register program model. Namely, they constructed a uniform family of register programs that computes $x^n$ using $n$ registers and four accesses to $x$. Since then, determining the number of registers and input accesses required to compute a polynomial of a given degree has become a central question in the study of catalytic computation. On one hand, we prove that the four-access bound of Buhrman et al.\ is optimal: every passive-output register program computing a polynomial of degree greater than three requires at least four input accesses, independently of the number of registers. On the other hand, we show that their register bound is not optimal. For every $t\geq2$ and every field $K$ of characteristic $0$ or greater than $2t-1$, we construct a register program for $x^{2t-1}$ with four input accesses and $t$ registers. Our proofs rely on derivations and their exponential operators. This approach represents a register program as a series of exponential derivation operators, reducing register restoration to an operator identity. Finally, we use the uniform family of register programs to improve known trade-offs for catalytic streaming algorithms and register programs for matrix powering. The generalization of the lower-bound methods and the construction of the uniform family of register programs were developed with assistance from ChatGPT 5.6.

0.15

A Simple Algebraic Proof of the PCP Theorem

cs.CC ·2026-08-18 ·Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
publishedtheory similarity 0.60
Abstract · Fixed an error in Lemma 3.3 and modified the tests accordingly

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

0.32

Property Testing for Recursive Query Languages

cs.DB cs.LO ·2026-09-03 ·Isolde Adler, Carsten Lutz, Quentin Manière, Marcin Przybyłko, Lukas Schulze
published similarity 0.57
Abstract

In the context of database querying, property testing provides a framework for testing query answers with high confidence while inspecting only a sublinear part of the database, through completion queries and size queries. A fundamental result of Chen and Yoshida (2019) states that non-satisfaction of a Boolean conjunctive query $q$ is testable with a constant number of such queries and one-sided error if and only if $q$ is equivalent to an $α$-acyclic query. In this article, we initiate the study of property testing for recursive query languages, focusing on two-way regular path queries (2RPQs) and monadic Datalog. One of our main results is positive: non-answers to any 2RPQ are constant query testable with one-sided error. We extend this slightly to a certain class of monadic Datalog programs in which recursion is restricted to be linear and rule bodies must be $α$-acyclic. Turning towards unrestricted monadic Datalog, we next show that if a monadic Datalog program $Π$ is not equivalent to an $α$-acyclic program, then falsity of $Π$ is not constant query testable with one-sided error. This is under the assumption that all rule-bodies are self-join free. We leave open the case of monadic Datalog programs with $α$-acyclic rule bodies that are not restricted to linear recursion, but observe as a first step that there exist $α$-acyclic programs that are mildly non-linear and constant query testable with one-sided error.

0.28

On Optimal Encodings and Systematicity in Function-Correcting Codes

cs.IT ·2026-10-06 ·Charul Rajput, Kanchana Lokshmii Jagatti, B. Sundar Rajan
theory similarity 0.57
Abstract

Function-correcting codes (FCCs) protect the value of a function $f$ of the message against $t$ errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of $2t$ on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs $2t$. For a linear function $f$ and a fixed linear code $C$, let $d_f$ denote the minimum distance between codewords of messages with different function values. Different generator matrices of $C$ assign different codewords to the messages and can give different values of $d_f$. We study which generator matrix of $C$ gives the largest $d_f$. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of $C$. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of $C$ alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic $(f,t)$-FCC of length $n$ exists if and only if a condition depending on $f$ only through the size of its smaller preimage holds. For $t=1$, redundancy $1$ is sufficient for every nonconstant two-valued function on $\mathbb{F}_2^k$ with $k\ge 10$. For general $t$, redundancy $1$ suffices for all two-valued functions once $k$ is large enough, and for each $s<2t$ we give an upper bound on the threshold in $k$ beyond which redundancy $s$ suffices.

0.15

Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time

cs.DS math.OC ·2026-10-19 ·Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh
published similarity 0.56
Abstract · This paper is based on the STOC 2024 proceedings paper "A strongly polynomial algorithm for linear programs with at most two nonzero entries…

Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for these classes, one also needs to address two important technical issues: initialization and bit-complexity bounds. Standard IPM initialization techniques either require numerical estimates that cannot be obtained in the strongly polynomial model, or involve modifying the instance in ways that do not preserve the geometry of the original LP, potentially affecting the SLC. In this work, we present an initialization framework for interior point methods for linear programming, along with a rounding procedure that ensures the continued feasibility of the IPM. We develop a multistage scheme in which each stage can be initialized in strongly polynomial time given the output of the previous stage. Additionally, we address the challenge of controlling the bit complexity of each iterate throughout the algorithm. To this end, we show that it is possible to represent iterates as low-complexity convex combinations of vertices and extreme rays. Our combinatorial rounding step is independent of the algorithm in ADLNV 2025, and can be applied more broadly in the context of path-following methods.

0.30

Pseudo-solutions of polynomial systems and the lower bound problem for $\mbox{AC}^0[p]$-Frege systems

cs.CC math.LO ·2026-09-28 ·Jan Krajicek
theory similarity 0.56
Abstract · only change: author name spelling corrected

The problem to establish a lower bound for $\mbox{AC}^0[p]$-Frege refutations of a system of polynomial equations over ${\bf F}_p$ was in K. (2024) reduced to the existence of a pseudo-solution (a notion defined there) for the system. Here we reduce this further, for the system expressing the negation of the PHP, to a property of search trees querying values of linear maps on the vector space of low degree polynomials over ${\bf F}_p$.

0.35

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.56
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

Maltsev Constraint Satisfaction Problems and Deterministic Logspace With Counting

cs.CC ·2026-09-25 ·Dejan Delic, Ali Syed
theoryhot direction similarity 0.56
Abstract

In this article, we prove that the problem of solving $\operatorname{CSP}(\mathbf{A})$, where $\mathbf{A}$ is a finite relational template which admits a Maltsev polymorphism is in a specific complexity class DET, which is related to the complexity of computing the determinant of a matrix with integer entries. Such a class is intimately related to well-studied MOD-logspace classes in the theory of computational complexity. To prove this fact, we develop a new algorithm for solving syntactically simple binary instances of Maltsev constraint satisfaction problems, rather different from the well-known Bulatov-Dalmau algorithm, which does not require the explicit use or knowledge of a Maltsev polymorphism of the template but, rather, utilizes a graph whose vertices are 2-generated subuniverses of $\mathbb{A}$, where $\mathbb{A}$ is the Maltsev algebra parametrizing $\operatorname{CSP}(\mathbf{A})$. The theoretical importance of this algorithm is reflected in two facts: (1) it places the problem $ \operatorname{CSP}(\mathbf{A})$ in a complexity class related to the deterministic logspace with counting, which, in itself, has a strong connection to a variety of standard algorithmic problems in linear algebra, and (2) it only makes use of the relational structure of the template without the need for the explicit use of a compatible Maltsev polymorphism, depending entirely on the strong ``symmetry" of constraints compatible with such polymorphisms and the knowledge of 2-generated subuniverses of $\mathbb{A}$.

0.49