Arrow Research search

Author name cluster

Nils Vortmeier

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

MFCS Conference 2024 Conference Paper

Query Maintenance Under Batch Changes with Small-Depth Circuits

  • Samir Datta
  • Asif Khan 0009
  • Anish Mukherjee 0001
  • Felix Tschirbs
  • Nils Vortmeier
  • Thomas Zeume

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 maintaining many important queries, among them reachability, tree isomorphism, and the word problem for context-free languages. In other words, these queries are in the dynamic complexity class DynFO. We show that most of the existing results for constant-size changes can be recovered for batch changes of polylogarithmic size if one allows circuits of depth 𝒪(log log n) or, equivalently, first-order updates that are iterated 𝒪(log log n) times.

Details

MFCS Conference 2024 Conference Paper

Specification and Automatic Verification of Computational Reductions

  • Julien Grange
  • Fabian Vehlken
  • Nils Vortmeier
  • Thomas Zeume

We are interested in the following validation problem for computational reductions: for algorithmic problems P and P^⋆, is a given candidate reduction indeed a reduction from P to P^⋆? Unsurprisingly, this problem is undecidable even for very restricted classes of reductions. This leads to the question: Is there a natural, expressive class of reductions for which the validation problem can be attacked algorithmically? We answer this question positively by introducing an easy-to-use graphical specification mechanism for computational reductions, called cookbook reductions. We show that cookbook reductions are sufficiently expressive to cover many classical graph reductions and expressive enough so that SAT remains NP-complete (in the presence of a linear order). Surprisingly, the validation problem is decidable for natural and expressive subclasses of cookbook reductions.

Details

CSL Conference 2023 Conference Paper

Dynamic Complexity of Regular Languages: Big Changes, Small Work

  • Felix Tschirbs
  • Nils Vortmeier
  • Thomas Zeume

Whether a changing string is member of a certain regular language can be maintained in the DynFO framework of Patnaik and Immerman: after changing the symbol at one position of the string, a first-order update formula can express - using additionally stored information - whether the resulting string is in the regular language. We extend this and further known results by considering changes of many positions at once. We also investigate to which degree the obtained update formulas imply work-efficient parallel dynamic algorithms.

Details

CSL Conference 2020 Conference Paper

Dynamic Complexity Meets Parameterised Algorithms

  • Jonas Schmidt 0001
  • Thomas Schwentick
  • Nils Vortmeier
  • Thomas Zeume
  • Ioannis Kokkinis

Dynamic Complexity studies the maintainability of queries with logical formulas in a setting where the underlying structure or database changes over time. Most often, these formulas are from first-order logic, giving rise to the dynamic complexity class DynFO. This paper investigates extensions of DynFO in the spirit of parameterised algorithms. In this setting structures come with a parameter k and the extensions allow additional "space" of size f(k) (in the form of an additional structure of this size) or additional time f(k) (in the form of iterations of formulas) or both. The resulting classes are compared with their non-dynamic counterparts and other classes. The main part of the paper explores the applicability of methods for parameterised algorithms to this setting through case studies for various well-known parameterised problems.

Details

CSL Conference 2020 Conference Paper

Dynamic Complexity of Parity Exists Queries

  • Nils Vortmeier
  • Thomas Zeume

Given a graph whose nodes may be coloured red, the parity of the number of red nodes can easily be maintained with first-order update rules in the dynamic complexity framework DynFO of Patnaik and Immerman. Can this be generalised to other or even all queries that are definable in first-order logic extended by parity quantifiers? We consider the query that asks whether the number of nodes that have an edge to a red node is odd. Already this simple query of quantifier structure parity-exists is a major roadblock for dynamically capturing extensions of first-order logic. We show that this query cannot be maintained with quantifier-free first-order update rules, and that variants induce a hierarchy for such update rules with respect to the arity of the maintained auxiliary relations. Towards maintaining the query with full first-order update rules, it is shown that degree-restricted variants can be maintained.

Details

Highlights Conference 2018 Conference Abstract

Reachability and Distances under Multiple Changes

  • Nils Vortmeier

ABSTRACT. Recently it was shown that the transitive closure of a directed graph can be updated using first-order formulas after insertions and deletions of single edges in the dynamic descriptive complexity framework by Dong, Su, and Topor, and Patnaik and Immerman. In other words, Reachability is in DynFO. In this talk we extend the framework to changes of multiple edges at a time, and study the Reachability and Distance queries under these changes. We show that the former problem can be maintained in DynFO(+, \times) under changes affecting O(log n / log log n) nodes, for graphs with n nodes. If the update formulas may use a majority quantifier then both Reachability and Distance can be maintained under changes that affect O(log^c n) nodes, for any fixed natural number c. This talk is based on a paper with the same title, presented at ICALP 2018, which is joint work with Samir Datta, Anish Mukherjee and Thomas Zeume.

Details

Highlights Conference 2016 Conference Abstract

Dynamic descriptive complexity of FO-definable modifications

  • Thomas Schwentick
  • Nils Vortmeier
  • Thomas Zeume

A dynamic program, as introduced by Dong, Su and Topor and Patnaik and Immerman, maintains the result of a fixed query for an input database which is subject to modifications. It can use an auxiliary database whose relations are updated via first-order formulas upon modifications of the input database. In the original setting, only insertions and deletions of single tuples are considered. In this talk, which is based on joint work with Thomas Schwentick and Thomas Zeume, we will allow modifications defined by (restricted) first-order formulas and review which queries can still be maintained. This talk is based on so far unpublished work.

Details

CSL Conference 2015 Conference Paper

Static Analysis for Logic-based Dynamic Programs

  • Thomas Schwentick
  • Nils Vortmeier
  • Thomas Zeume

The goal of dynamic programs as introduced by Patnaik and Immerman (1994) is to maintain the result of a fixed query for an input database which is subject to tuple insertions and deletions. To this end such programs store an auxiliary database whose relations are updated via first-order formulas upon modifications of the input database. One of those auxiliary relations is supposed to store the answer to the query. Several static analysis problems can be associated to such dynamic programs. Is the answer relation of a given dynamic program always empty? Does a program actually maintain a query? That is, is the answer given of the program the same when an input database was reached by two different modification sequences? Even more, is the content of auxiliary relations independent of the modification sequence that lead to an input database? We study the algorithmic properties of those and similar static analysis problems. Since all these problems can easily be seen to be undecidable for full first-order programs, we examine the exact borderline for decidability for restricted programs. Our focus is on restricting the arity of the input databases as well as the auxiliary databases, and to restrict the use of quantifiers.

Details
v2026.09.13