A5047583476- Complexity and Algorithms in Graphs
- Optimization and Search Problems
- Semantic Web and Ontologies
- Advanced Graph Theory Research
- Advanced Database Systems and Queries
- Cryptography and Data Security
- Data Management and Algorithms
- Biomedical Text Mining and Ontologies
- Natural Language Processing Techniques
- Distributed systems and fault tolerance
- Privacy-Preserving Technologies in Data
- Service-Oriented Architecture and Web Services
- Stochastic Gradient Optimization Techniques
- semigroups and automata theory
- Computability, Logic, AI Algorithms
- Auction Theory and Applications
- Logic, Reasoning, and Knowledge
- Cardiac, Anesthesia and Surgical Outcomes
- Biomedical and Chemical Research
- Machine Learning and Algorithms
- Nausea and vomiting management
- Software-Defined Networks and 5G
- Distributed and Parallel Computing Systems
- DNA and Biological Computing
- Business Process Modeling and Analysis
Helmholtz Center for Information Security
2021-2024
Gran Sasso Science Institute
2024
Leibniz Institute for Neurobiology
2021-2022
ETH Zurich
2015-2021
Vatican Secret Archives
2021
Grammar School
2021
Eötvös Loránd University
2021
Masaryk University
2021
National University of Singapore
2021
Siemens (Germany)
2015-2019
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires Omega(log log n) communication rounds, assuming it finds a correct assignment with high probability. Our result holds even in special case of d = O(1), where is maximum degree dependency graph. By prior work, there are algorithms running time O(log rounds bounded-degree graphs, and best lower bound before our work was Omega(log* [Chung et al. 2014].
We study consistent migration of flows, with special focus on software defined networks. Given a current and desired network flow configuration, we give the first polynomial-time algorithm to decide if congestion-free is possible. However, all flows must be integer or are unsplittable, this NP-hard decide. A similar problem providing increased bandwidth an application, while keeping other in network, but possibly migrating them consistently paths. show that maximum increase can approximated...
An important application of semantic technologies in industry has been the formalisation information models using OWL 2 ontologies and use RDF for storing exchanging data. Moreover, legacy data can be virtualised as following ontology-based ac cess (OBDA) approach. In all these applications, it is to provide domain experts with query formulation tools expressing their needs terms queries over ontologies. this work, we present such a tool, OptiqueVQS, which designed based on our experience...
We advocate datalogMTL, a datalog extension of Horn fragment the metric temporal logic MTL, as language for ontology-based access to log data. show that datalogMTL is EXPSPACE-complete even with punctual intervals, in which case MTL known be undecidable. Nonrecursive turns out PSPACE-complete combined complexity and AC0 data complexity. demonstrate by two real-world use cases nonrecursive programs can express complex concepts from typical user queries thereby facilitate Our experiments...
There are distributed graph algorithms for finding maximal matchings and independent sets in O(Δ + log^* n) communication rounds; here n is the number of nodes Δ maximum degree. The lower bound by Linial (1987, 1992) shows that dependency on optimal: these problems cannot be solved o(log^* rounds even if = 2. However, a long-standing open question, there currently an exponential gap between upper bounds. We prove bounds tight. show found o(Δ log / with any randomized algorithm LOCAL model...

 We propose a novel framework for ontology-based access to temporal log data using datalog extension datalogMTL of the Horn fragment metric logic MTL. show that is EXPSPACE-complete even with punctual intervals, in which case full MTL known be undecidable. also prove nonrecursive PSPACE-complete combined complexity and AC0 complexity. demonstrate by two real-world use cases programs can express complex concepts from typical user queries thereby facilitate data. Our experiments Siemens...
Real-time processing of data coming from multiple heterogeneous streams and static databases is a typical task in many industrial scenarios such as diagnostics large machines. A complex diagnostic may require collection up to hundreds queries over data. Although these retrieve the same kind, temperature measurements, they access structurally different sources. In this work we show how Semantic Technologies implemented our system optique can simplify by providing an abstraction...
Recently, Brandt et al.\ [STOC'16] proved a lower bound for the distributed Lovász Local Lemma, which has been conjectured to be tight sufficiently relaxed LLL criteria by Chang and Pettie [FOCS'17]. At heart of their result lies speedup technique that, graphs girth at least 2t+2, transforms any t-round algorithm one specific problem into (t-1)-round same problem. We substantially improve on this showing that such exists locally checkable ¶i, with difference ¶i_1 inferred solves is not...
The last five years of research on distributed graph algorithms have seen huge leaps progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds emerged for many central problems exponential over the state art been achieved runtimes algorithms. Nevertheless, there are still large gaps between best known upper important problems. current bound techniques deterministic often tailored to obtaining a logarithmic essentially cannot be used prove beyond...
There has been major progress both in description logics and ontology design since SNOMED was originally developed. The emergence of the standard Web Ontology language its latest revision, OWL 1.1 is leading to a rapid proliferation tools. Combined with increase computing power past two decades, these developments mean that many restrictions limited SNOMED's original formulation no longer need apply. We argue difficulties identified could be more easily dealt using expressive than which...
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained lot importance, especially in the context classic graph problems. In this work, we mainly consider maximal matching independent set problems MPC model.
An increasing number of sensors are being deployed in business-critical environments, systems, and equipment; stream a vast amount data. The operational efficiency effectiveness business processes rely on domain experts' agility interpreting data into actionable informatio n. A expert has extensive knowledge but not necessarily skills databases formal query languages. Therefore, centralised approaches often preferred. These require IT experts to translate the information needs...
ABSTRACT Recent pike-like predatory fishes attack prey animals by a quick strike out of rest or slow movement. This fast-start behaviour includes preparatory, propulsive and final phase, the latter is crucial for success attack. To prevent from escape, predators tend to minimise duration interaction disturbance caused surrounding water in order not be detected prey's lateral line sensory system. We compared hydrodynamic properties earliest fossil representative morphotype, Triassic...
LCLs or locally checkable labelling problems (e.g. maximal independent set, matching, and vertex colouring) in the LOCAL model of computation are very well-understood cycles (toroidal 1-dimensional grids): every problem has a complexity O(1), Θ(log* n), Θ(n), design optimal algorithms can be fully automated. This work develops theory LCL for toroidal 2-dimensional grids. The classes same as case: Θ(n). However, given an it is undecidable whether its n) Θ(n)