139 citations · 168 across the 14 of their papers we have counts for
14 papers · 1 filter
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…
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…
Probabilistic Generating Circuits -- Demystified
Sanyam Agarwal, Markus Bläser
Zhang et al. (ICML 2021, PLMR 139, pp. 12447-1245) introduced probabilistic generating circuits (PGCs) as a probabilistic model to unify probabilistic circuits (PCs) and determinan…
PosSLP and Sum of Squares
Markus Bläser, Julian Dörfler, Gorav Jindal
The problem PosSLP is the problem of determining whether a given straight-line program (SLP) computes a positive integer. PosSLP was introduced by Allender et al. to study the comp…
Algebraic Branching Programs, Border Complexity, and Tangent Spaces
Markus Bläser, Christian Ikenmeyer, Meena Mahajan +2
Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks…
On the complexity of evaluating highest weight vectors
Markus Bläser, Julian Dörfler, Christian Ikenmeyer
Geometric complexity theory (GCT) is an approach towards separating algebraic complexity classes through algebraic geometry and representation theory. Originally Mulmuley and Sohon…
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov +2
We study the variety membership testing problem in the case when the variety is given as an orbit closure and the ambient space is the set of all 3-tensors. The first variety that…
Parameterized Valiant's Classes
Markus Blaeser, Christian Engels
We define a theory of parameterized algebraic complexity classes in analogy to parameterized Boolean counting classes. We define the classes VFPT and VW[t], which mirror the Boolea…
Graph Pattern Polynomials
Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
We study the time complexity of induced subgraph isomorphism problems where the pattern graph is fixed. The earliest known example of an improvement over trivial algorithms is by I…
The border support rank of two-by-two matrix multiplication is seven
Markus Bläser, Matthias Christandl, Jeroen Zuiddam
We show that the border support rank of the tensor corresponding to two-by-two matrix multiplication is seven over the complex numbers. We do this by constructing two polynomials t…
On degeneration of tensors and algebras
Markus Bläser, Vladimir Lysikov
An important building block in all current asymptotically fast algorithms for matrix multiplication are tensors with low border rank, that is, tensors whose border rank is equal or…
Smoothed Complexity Theory
Markus Bläser, Bodo Manthey
Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng (J. ACM, 2004). Classical methods like worst-case or average-case analysis have accompanying…
On the Complexity of the Interlace Polynomial
Markus Bläser, Christian Hoffmann
We consider the two-variable interlace polynomial introduced by Arratia, Bollobas and Sorkin (2004). We develop graph transformations which allow us to derive point-to-point reduct…