139 citations · 168 across the 14 of their papers we have counts for
23 papers
Verifiable quantum advantage based on polynomials with planted structures
Markus Bläser, Michael Gullans, Dominik Hangleiter +2
A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also v…
The Complexity of Bisimilarity and Model Checking in Finitary Diagrams
Markus Bläser, Sagnik Dutta, Samuel Okyay
Inspired by the work of Dubut, Goubault, and Goubault-Larrecq (ICALP 2015) on natural homology, Dubut (RAMiCS 2020) introduces finitary diagrams and studies bisimilarity and diagra…
On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
Sanyam Agarwal, Markus Bläser, Mridul Gupta
Barvinok introduced the symmetrized determinant ($\sdet$) as a \emph{non-commutative} analogue of the determinant. Intuitively, given a square matrix over an associative algebra, w…
Exponential lower bound via exponential sums
Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta +1
Valiant's famous VP vs. VNP conjecture states that the symbolic permanent polynomial does not have polynomial-size algebraic circuits. However, the best upper bound on the size of…
On the Complexity of Identification in Linear Structural Causal Models
Julian Dörfler, Benito van der Zander, Markus Bläser +1
Learning the unknown causal parameters of a linear structural causal model is a fundamental task in causal analysis. The task, known as the problem of identification, asks to estim…
The Existential Theory of the Reals with Summation Operators
Markus Bläser, Julian Dörfler, Maciej Liskiewicz +1
To characterize the computational complexity of satisfiability problems for probabilistic and causal reasoning within the Pearl's Causal Hierarchy, arXiv:2305.09508 [cs.AI] introdu…