Zobrazeno 1 - 10
of 38
pro vyhledávání: '"Vortmeier, Nils"'
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,
Externí odkaz:
http://arxiv.org/abs/2407.20031
We are interested in the following validation problem for computational reductions: for algorithmic problems $P$ and $P^\star$, is a given candidate reduction indeed a reduction from $P$ to $P^\star$? Unsurprisingly, this problem is undecidable even
Externí odkaz:
http://arxiv.org/abs/2407.04037
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. Figaro's main novelty is that it pushes the QR decomposition past the join.
Externí odkaz:
http://arxiv.org/abs/2204.00525
Autor:
Vortmeier, Nils, Kokkinis, Ioannis
Finding a homomorphism from some hypergraph $\mathcal{Q}$ (or some relational structure) to another hypergraph $\mathcal{D}$ is a fundamental problem in computer science. We show that an answer to this problem can be maintained under single-edge chan
Externí odkaz:
http://arxiv.org/abs/2107.06121
Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering membership and range queries for formal languages in parallel constant time
Externí odkaz:
http://arxiv.org/abs/2101.08735
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was extended for changes of size $\frac{\log n}{\log \log n}$, where $n$ is th
Externí odkaz:
http://arxiv.org/abs/2004.12739
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 cl
Externí odkaz:
http://arxiv.org/abs/1910.06281
Autor:
Vortmeier, Nils, Zeume, Thomas
Publikováno v:
Logical Methods in Computer Science, Volume 17, Issue 4 (November 16, 2021) lmcs:6639
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 al
Externí odkaz:
http://arxiv.org/abs/1910.06004
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 Imm
Externí odkaz:
http://arxiv.org/abs/1804.08555
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 2 (May 8, 2019) lmcs:4515
In the setting of DynFO, dynamic programs update the stored result of a query whenever the underlying data changes. This update is expressed in terms of first-order logic. We introduce a strategy for constructing dynamic programs that utilises period
Externí odkaz:
http://arxiv.org/abs/1704.07998