6 citations · 10 across the 3 of their papers we have counts for
6 papers · 1 filter
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…
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…