5 citations · 17 across the 20 of their papers we have counts for
24 papers
Unifying and Extending Strong Simulation of Quantum Circuits
Floris Geerts, Rihan Hai, Matthias Lanzinger +3
We establish functional aggregate queries (FAQs) as a unifying language for exact classical simulation of quantum circuits. A circuit becomes a sum-product query: factors encode ga…
FPT=PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns
Matthias Lanzinger
Assuming the Exponential Time Hypothesis (ETH), fixed-parameter tractability and polynomial-time solvability coincide for homomorphism problems specified by classes of pattern hype…
Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler--Leman and Hypertree Width
Panagiotis Aivasiliotis, Andreas Göbel, Matthias Lanzinger +1
The Weisfeiler--Leman (WL) algorithm is one of the most influential heuristics for the graph isomorphism problem. The expressive power of WL has been extensively studied in the con…
Cuts and Gauges for Submodular Width
Matthias Lanzinger
Submodular width is a central structural measure governing the complexity of conjunctive query evaluation. In this paper we recast submodular width in geometric terms. We how that…
From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
Markus Hecher, Matthias Lanzinger
Counting problems are fundamental across mathematics and computer science. Among the most subtle are those whose associated decision problem is solvable in polynomial time, yet who…
FPT Parameterisations of Fractional and Generalised Hypertree Width
Matthias Lanzinger, Igor Razgon, Daniel Unterberger
We present the first fixed-parameter tractable (FPT) algorithms for exact computation of generalized hypertree width (ghw) and fractional hypertree width (fhw). Our algorithms are…
Selective Use of Yannakakis' Algorithm to Improve Query Performance: Machine Learning to the Rescue
Daniela Böhm, Georg Gottlob, Matthias Lanzinger +4
Query optimization has played a central role in database research for decades. However, more often than not, the proposed optimization techniques lead to a performance improvement…
Soft and Constrained Hypertree Width
Matthias Lanzinger, Cem Okulmus, Reinhard Pichler +2
Hypertree decompositions provide a way to evaluate Conjunctive Queries (CQs) in polynomial time, where the exponent of this polynomial is determined by the width of the decompositi…
Avoiding Materialisation for Guarded Aggregate Queries
Matthias Lanzinger, Reinhard Pichler, Alexander Selzer
Optimising queries with many joins is known to be a hard problem. The explosion of intermediate results as opposed to a much smaller final result poses a serious challenge to moder…
Fuzzy Datalog over Arbitrary t-Norms
Matthias Lanzinger, Stefano Sferrazza, Przemysław A. Wałęga +1
One of the main challenges in the area of Neuro-Symbolic AI is to perform logical reasoning in the presence of both neural and symbolic data. This requires combining heterogeneous…
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
Matthias Lanzinger, Igor Razgon
Generalised hypertree width () is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing of a…
Structure-Guided Query Evaluation: Towards Bridging the Gap from Theory to Practice
Georg Gottlob, Matthias Lanzinger, Davide Mario Longo +3
Join queries involving many relations pose a severe challenge to today's query optimisation techniques. To some extent, this is due to the fact that these techniques do not pay suf…
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, Marc Roth
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs and , count the number of copies of in .…
Incremental Updates of Generalized Hypertree Decompositions
Georg Gottlob, Matthias Lanzinger, Davide Mario Longo +1
Structural decomposition methods, such as generalized hypertree decompositions, have been successfully used for solving constraint satisfaction problems (CSPs). As decompositions c…
Generative Datalog with Stable Negation
Mario Alviano, Matthias Lanzinger, Michael Morak +1
Extending programming languages with stochastic behaviour such as probabilistic choices or random sampling has a long tradition in computer science. A recent development in this di…
MV-Datalog+-: Effective Rule-based Reasoning with Uncertain Observations
Matthias Lanzinger, Stefano Sferrazza, Georg Gottlob
Modern applications combine information from a great variety of sources. Oftentimes, some of these sources, like Machine-Learning systems, are not strictly binary but associated wi…
The Complexity of Conjunctive Queries with Degree 2
Matthias Lanzinger
We study the tractability of conjunctive query answering for queries with unbounded arity. It is well known that tractability of the problem can be characterised in terms of the qu…
On the Complexity of Inductively Learning Guarded Rules
Andrei Draghici, Georg Gottlob, Matthias Lanzinger
We investigate the computational complexity of mining guarded clauses from clausal datasets through the framework of inductive logic programming (ILP). We show that learning guarde…
The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions
Georg Gottlob, Matthias Lanzinger, Davide Mario Longo +2
Constraint Satisfaction Problems (CSPs) play a central role in many applications in Artificial Intelligence and Operations Research. In general, solving CSPs is NP-complete. The st…
Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems
Hubie Chen, Georg Gottlob, Matthias Lanzinger +1
Constraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e.g., coloring or scheduling problems. Solving CS…
Tractability Beyond -Acyclicity for Conjunctive Queries with Negation
Matthias Lanzinger
Numerous fundamental database and reasoning problems are known to be NP-hard in general but tractable on instances where the underlying hypergraph structure is -acyclic. Despite…
Fractional Covers of Hypergraphs with Bounded Multi-Intersection
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler +1
Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. Th…
Complexity Analysis of Generalized and Fractional Hypertree Decompositions
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler +1
Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hy…
Semantic Width of Conjunctive Queries and Constraint Satisfaction Problems
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler
Answering Conjunctive Queries (CQs) and solving Constraint Satisfaction Problems (CSPs) are arguably among the most fundamental tasks in Computer Science. They are classical NP-com…