5 citations · 17 across the 20 of their papers we have counts for
4 papers · 1 filter
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…