2 citations · 3 across the 2 of their papers we have counts for
7 papers
Which graph motif parameters count?
Markus Bläser, Radu Curticapean, Julian Dörfler +1
For a fixed graph H, the function #IndSub(H,*) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interp…
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…
Functional Closure Properties of Finite -weighted Automata
Julian Dörfler, Christian Ikenmeyer
We determine all functional closure properties of finite -weighted automata, even all multivariate ones, and in particular all multivariate polynomials. We also determi…
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…
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…
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
Julian Dörfler, Marc Roth, Johannes Schmitt +1
We study the problem #IndSub(P) of counting all induced subgraphs of size k in a graph G that satisfy the property P. This problem was introduced by Jerrum and Meeks and shown to b…