3 citations · 8 across the 7 of their papers we have counts for
15 papers
Dynamic Planar Graph Isomorphism is in DynFO
Samir Datta, Asif Khan, Felix Tschirbs +2
Consider two planar graphs which are subject to edge insertions and deletions. We show that whether the two graphs are isomorphic can be maintained with first-order logic formulas…
Algebraic Characterizations of Classes of Regular Languages in DynFO
Corentin Barloy, Felix Tschirbs, Nils Vortmeier +1
This paper explores the fine-grained structure of classes of regular languages maintainable in fragments of first-order logic within the dynamic descriptive complexity framework of…
Query maintenance under batch changes with small-depth circuits
Samir Datta, Asif Khan, Anish Mukherjee +3
Which dynamic queries can be maintained efficiently? For constant-size changes, it is known that constant-depth circuits or, equivalently, first-order updates suffice for maintaini…
Specification and Automatic Verification of Computational Reductions
Julien Grange, Fabian Vehlken, Nils Vortmeier +1
We are interested in the following validation problem for computational reductions: for algorithmic problems and , is a given candidate reduction indeed a reduction fr…
Givens Rotations for QR Decomposition, SVD and PCA over Database Joins
Dan Olteanu, Nils Vortmeier, Đorđe Živanović
This article introduces Figaro, an algorithm for computing the upper-triangular matrix in the QR decomposition of the matrix defined by the natural join over relational data. Figar…
The Dynamic Complexity of Acyclic Hypergraph Homomorphisms
Nils Vortmeier, Ioannis Kokkinis
Finding a homomorphism from some hypergraph (or some relational structure) to another hypergraph is a fundamental problem in computer science. We show t…