Markus Bläser

NeurIPS Conference 2025 Conference Paper

Faster Generic Identification in Tree-Shaped Structural Causal Models

• Yasmine Briefs
• Markus Bläser

Linear structural causal models (SCMs) are used to analyze the relationships between random variables. Directed edges represent direct causal effects and bidirected edges represent hidden confounders. Generically identifying the causal parameters from observed correlations between the random variables is an open problem in causality. Gupta and Bl\"aser solve the case of SCMs in which the directed edges form a tree by giving a randomized polynomial time algorithm with running time $O(n^6)$. We present an improved algorithm with running time $O(n^3 \log^2 n)$ and demonstrate its feasibility by providing an implementation that outperforms existing state-of-the-art implementations.

ICLR Conference 2025 Conference Paper

From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy

• Julian Dörfler
• Benito van der Zander
• Markus Bläser
• Maciej Liskiewicz

The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reasoning: probabilistic (i.e. purely observational), interventional, and counterfactual, that reflect the progressive sophistication of human thought regarding causation. We investigate the computational complexity aspects of reasoning in this framework focusing mainly on satisfiability problems expressed in probabilistic and causal languages across the PCH. That is, given a system of formulas in the standard probabilistic and causal languages, does there exist a model satisfying the formulas? Our main contribution is to prove the exact computational complexities showing that languages allowing addition and marginalization (via the summation operator) yield NP^{PP}-, PSPACE-, and NEXP-complete satisfiability problems, depending on the level of the PCH. These are the first results to demonstrate a strictly increasing complexity across the PCH: from probabilistic to causal and counterfactual reasoning. On the other hand, in the case of full languages, i.e.~allowing addition, marginalization, and multiplication, we show that the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels, solving an open problem in the field.

ICML Conference 2025 Conference Paper

The Limits of Tractable Marginalization

• Oliver Broadrick
• Sanyam Agarwal
• Guy Van den Broeck
• Markus Bläser

Marginalization – summing a function over all assignments to a subset of its inputs – is a fundamental computational problem with applications from probabilistic inference to formal verification. Despite its computational hardness in general, there exist many classes of functions (e. g. , probabilistic models) for which marginalization remains tractable, and they can all be commonly expressed by arithmetic circuits computing multilinear polynomials. This raises the question, can all functions with polynomial time marginalization algorithms be succinctly expressed by such circuits? We give a negative answer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming $\\mathsf{FP} \\neq \#\\mathsf{P}$ (an assumption implied by $\\mathsf{P} \\neq \\mathsf{NP}$). To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known circuit models. We conclude with a completeness result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small arithmetic circuits for that function’s multilinear representation.

MFCS Conference 2025 Conference Paper

Which Graph Motif Parameters Count?

• Markus Bläser
• Radu Curticapean
• Julian Dörfler
• Christian Ikenmeyer

For a fixed graph H, the function #Ind(H → ⋆) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interpretation. Linear combinations of such functions are called graph motif parameters and have recently received significant attention in counting complexity after a seminal paper by Curticapean, Dell and Marx (STOC'17). We show that, among linear combinations of functions #Ind(H → ⋆) involving only graphs H without isolated vertices, precisely those with positive integer coefficients maintain a combinatorial interpretation. It is important to note that graph motif parameters can be nonnegative for all inputs G, even when some coefficients are negative. Formally, we show that evaluating any graph motif parameter with a negative coefficient is impossible in an oracle variant of #P, where an implicit graph is accessed by oracle queries. Our proof follows the classification of the relativizing closure properties of #P by Hertrampf, Vollmer, and Wagner (SCT'95) and the framework developed by Ikenmeyer and Pak (STOC'22), but our application of the required Ramsey theorem turns out to be more subtle, as graphs do not have the required Ramsey property. Our techniques generalize from graphs to relational structures, including colored graphs. Vastly generalizing this, we introduce motif parameters over categories that count occurrences of sub-objects in the category. We then prove a general dichotomy theorem that characterizes which such parameters have a combinatorial interpretation. Using known results in Ramsey theory for categories, we obtain a dichotomy for motif parameters of finite vector spaces as well as parameter sets.

AAAI Conference 2024 Conference Paper

Identification for Tree-Shaped Structural Causal Models in Polynomial Time

• Aaryan Gupta
• Markus Bläser

Linear structural causal models (SCMs) are used to express and analyze the relationships between random variables. Direct causal effects are represented as directed edges and confounding factors as bidirected edges. Identifying the causal parameters from correlations between the nodes is an open problem in artificial intelligence. In this paper, we study SCMs whose directed component forms a tree. Van der Zander et al. give a PSPACE-algorithm for the identification problem in this case, which is a significant improvement over the general Gröbner basis approach, which has doubly-exponential time complexity in the number of structural parameters. However, they do not show that their algorithm is complete. In this work, we present a randomized polynomial-time algorithm, which solves the identification problem for tree-shaped SCMs. For every structural parameter, our algorithms decides whether it is generically identifiable, generically 2-identifiable, or generically unidentifiable. (No other cases can occur.) In the first two cases, it provides one or two fractional affine square root terms of polynomials (FASTPs) for the corresponding parameter, respectively. In particular, our algorithm is not only polynomial time, but also complete for for tree-shaped SCMs.

NeurIPS Conference 2024 Conference Paper

On the Complexity of Identification in Linear Structural Causal Models

• Julian Dörfler
• Benito van der Zander
• Markus Bläser
• Maciej Liśkiewicz

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 estimate the parameters of the model from acombination of assumptions on the graphical structure of the model and observational data, represented as a non-causal covariance matrix. In this paper, we give a new sound and complete algorithm for generic identification which runs in polynomial space. By a standard simulation result, namely $\mathsf{PSPACE} \subseteq \mathsf{EXP}$, this algorithm has exponential running time which vastly improves the state-of-the-art double exponential time method using a Gröbner basis approach. The paper also presents evidence that parameter identification is computationally hard in general. In particular, we prove, that the taskasking whether, for a given feasible correlation matrix, there are exactly one or two or more parameter sets explaining the observed matrix, is hard for $\forall \mathbb{R}$, the co-class of the existential theory of the reals. In particular, this problem is $\mathsf{coNP}$-hard. To our best knowledge, this is the first hardness result for some notion of identifiability.

ICML Conference 2024 Conference Paper

Probabilistic Generating Circuits - Demystified

• Sanyam Agarwal
• Markus Bläser

Zhang et al. (ICML 2021, PLMR 139, pp. 12447–12457) introduced probabilistic generating circuits (PGCs) as a probabilistic model to unify probabilistic circuits (PCs) and determinantal point processes (DPPs). At a first glance, PGCs store a distribution in a very different way, they compute the probability generating polynomial instead of the probability mass function and it seems that this is the main reason why PGCs are more powerful than PCs or DPPs. However, PGCs also allow for negative weights, whereas classical PCs assume that all weights are nonnegative. One main insight of this work is that the negative weights are the cause for the power of PGCs and not the different representation. PGCs are PCs in disguise: we show how to transform any PGC on binary variables into a PC with negative weights with only polynomial blowup. PGCs were defined by Zhang et al. only for binary random variables. As our second main result, we show that there is a good reason for this: we prove that PGCs for categorical variables with larger image size do not support tractable marginalization unless NP=P. On the other hand, we show that we can model categorical variables with larger image size as PC with negative weights computing set-multilinear polynomials. These allow for tractable marginalization. In this sense, PCs with negative weights strictly subsume PGCs.

ICML Conference 2023 Conference Paper

Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits

• Markus Bläser

Probabilistic modeling is a central task in machine learning. Probabilistic models should be tractable, i. e. , allowing tractable probabilistic inference, but also efficient, i. e. , being able to represent a large set of probability distributions. Zhang et al. (ICML 2021) recently proposed a new model, probabilistic generating circuits. They raised the question whether every strongly Rayleigh distribution can be efficiently represented by such circuits. We prove that this question has a negative answer, there are strongly Rayleigh distributions that cannot be represented by polynomial-sized probabilistic generating circuits, assuming a widely accepted complexity theoretic conjecture.

IJCAI Conference 2023 Conference Paper

The Hardness of Reasoning about Probabilities and Causality

• Benito van der Zander
• Markus Bläser
• Maciej Liśkiewicz

We study formal languages which are capable of fully expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects, from a computational complexity perspective. We focus on satisfiability problems whose instance formulas allow expressing many tasks in probabilistic and causal inference. The main contribution of this work is establishing the exact computational complexity of these satisfiability problems. We introduce a new natural complexity class, named succ∃R, which can be viewed as a succinct variant of the well-studied class ∃R, and show that these problems are complete for succ∃R. Our results imply even stronger limitations on the use of algorithmic methods for reasoning about probabilities and causality than previous state-of-the-art results that rely only on the NP- or ∃R-completeness of the satisfiability problems for some restricted languages.

SODA Conference 2021 Conference Paper

On the Orbit Closure Containment Problem and Slice Rank of Tensors

• Markus Bläser
• Christian Ikenmeyer
• Vladimir Lysikov
• Anurag Pandey 0001
• Frank-Olaf Schreyer

We consider the orbit closure containment problem, which, for a given vector and a group orbit, asks if the vector is contained in the closure of the group orbit. Recently, many algorithmic problems related to orbit closures have proved to be quite useful in giving polynomial time algorithms for special cases of the polynomial identity testing problem and several non-convex optimization problems. Answering a question posed by Wigderson, we show that the algorithmic problem corresponding to the orbit closure containment problem is NP-hard. We show this by establishing a computational equivalence between the solvability of homogeneous quadratic equations and a homogeneous version of the matrix completion problem, while showing that the latter is an instance of the orbit closure containment problem. Secondly, we consider the notion of slice rank of tensors, which was recently introduced by Tao, and has subsequently been used for breakthroughs in several combinatorial problems like capsets, sunflower free sets, tri-colored sum-free sets, and progression-free sets. We show that the corresponding algorithmic problem, which can also be phrased as a problem about union of orbit closures, is also NP-hard, hence answering an open question by Bürgisser, Garg, Oliveira, Walter, and Wigderson. We show this by using a connection between the slice rank and the size of a minimum vertex cover of a hypergraph revealed by Tao and Sawin.

MFCS Conference 2020 Conference Paper

Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras

• Markus Bläser
• Vladimir Lysikov

Determining the exponent of matrix multiplication ω is one of the central open problems in algebraic complexity theory. All approaches to design fast matrix multiplication algorithms follow the following general pattern: We start with one "efficient" tensor T of fixed size and then we use a way to get a large matrix multiplication out of a large tensor power of T. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over C: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. To obtain our result, we relate irreversibility to asymptotic slice rank and instability of tensors and prove that the instability of block tensors can often be decided by looking only on the sizes of nonzero blocks.

SODA Conference 2019 Conference Paper

A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials

• Vishwas Bhargava
• Markus Bläser
• Gorav Jindal
• Anurag Pandey 0001

STOC Conference 2018 Conference Paper

Generalized matrix completion and algebraic natural proofs

• Markus Bläser
• Christian Ikenmeyer
• Gorav Jindal
• Vladimir Lysikov

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 653–664, 2017) and independently by Grochow, Kumar, Saks and Saraf (CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich’s famous barrier result (J. Comput. Syst. Sci., 55(1): 24–35, 1997) for Boolean circuit complexity to algebraic complexity theory. Razborov and Rudich’s barrier result relies on a widely believed assumption, namely, the existence of pseudo-random generators. Unfortunately, there is no known analogous theory of pseudo-randomness in the algebraic setting. Therefore, Forbes et al. use a concept called succinct hitting sets instead. This assumption is related to polynomial identity testing, but it is currently not clear how plausible this assumption is. Forbes et al. are only able to construct succinct hitting sets against rather weak models of arithmetic circuits.

MFCS Conference 2016 Conference Paper

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 very close to their size. To find new asymptotically fast algorithms for matrix multiplication, it seems to be important to understand those tensors whose border rank is as small as possible, so called tensors of minimal border rank. We investigate the connection between degenerations of associative algebras and degenerations of their structure tensors in the sense of Strassen. It allows us to describe an open subset of n*n*n tensors of minimal border rank in terms of smoothability of commutative algebras. We describe the smoothable algebra associated to the Coppersmith-Winograd tensor and prove a lower bound for the border rank of the tensor used in the "easy construction" of Coppersmith and Winograd.

I&C Journal 2015 Journal Article

Noncommutativity makes determinants hard

• Markus Bläser

We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that A is fixed. In this case, we obtain the following dichotomy: If A / rad A is noncommutative, then computing the determinant over A is hard. “Hard” here means # P -hard over fields of characteristic 0 and Mod p P -hard over fields of characteristic p > 0. If A / rad A is commutative and the underlying field is perfect, then we can compute the determinant over A in polynomial time. We also consider the case when A is part of the input. Here the hardness is closely related to the nilpotency index of the commutator ideal of A. Our work generalizes and builds upon previous papers by Arvind and Srinivasan (STOC 2010) [1] as well as Chien et al. (STOC 2011) [5].

MFCS Conference 2012 Conference Paper

Smoothed Complexity Theory

• Markus Bläser
• Bodo Manthey

Abstract 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 complexity classes, like P and Avg − P, respectively. While worst-case or average-case analysis give us a means to talk about the running time of a particular algorithm, complexity classes allows us to talk about the inherent difficulty of problems. Smoothed analysis is a hybrid of worst-case and average-case analysis and compensates some of their drawbacks. Despite its success for the analysis of single algorithms and problems, there is no embedding of smoothed analysis into computational complexity theory, which is necessary to classify problems according to their intrinsic difficulty. We propose a framework for smoothed complexity theory, define the relevant classes, and prove some first results.

MFCS Conference 2011 Conference Paper

The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree

• Markus Bläser
• Radu Curticapean

Abstract The cover polynomials are bivariate graph polynomials that can be defined as weighted sums over all path-cycle covers of a graph. In [3], a dichotomy result for the cover polynomials was proven, establishing that their evaluation is # P -hard everywhere but at a finite set of points, where evaluation is in FP. In this paper, we show that almost the same dichotomy holds when restricting the evaluation to planar graphs. We even provide hardness results for planar DAGs of bounded degree. For particular subclasses of planar graphs of bounded degree and for variants thereof, we also provide algorithms that allow for polynomial-time evaluation of the cover polynomials at certain new points by utilizing Valiant’s holographic framework.

TCS Journal 2009 Journal Article

Semisimple algebras of almost minimal rank over the reals

• Markus Bläser
• Andreas Meyer de Voltaire

A famous lower bound for the bilinear complexity of the multiplication in associative algebras is the Alder–Strassen bound. Algebras for which this bound is tight are called algebras of minimal rank. After 25 years of research, these algebras are now well understood. Here we start the investigation of the algebras for which the Alder–Strassen bound is off by one. As a first result, we completely characterize the semisimple algebras over R whose bilinear complexity is by one larger than the Alder–Strassen bound. Furthermore, we characterize all algebras A (with radical) of minimal rank plus one over R for which A / rad A has minimal rank plus one. The other possibility is that A / rad A has minimal rank. For this case, we only present a partial result.

MFCS Conference 2007 Conference Paper

Semisimple Algebras of Almost Minimal Rank over the Reals

• Markus Bläser
• Andreas Meyer de Voltaire

Abstract A famous lower bound for the bilinear complexity of the multiplication in associative algebras is the Alder–Strassen bound. Algebras for which this bound is tight are called algebras of minimal rank. After 25 years of research, these algebras are now well understood. We here start the investigation of the algebras for which the Alder–Strassen bound is off by one. As a first result, we completely characterize the semisimple algebras over ℝ whose bilinear complexity is by one larger than the Alder–Strassen bound.

TCS Journal 2005 Journal Article

Beyond the Alder–Strassen bound

• Markus Bläser

We prove a lower bound of 5 2 n 2 - 3 n for the multiplicative complexity of n × n -matrix multiplication over arbitrary fields. More general, we show that for any finite dimensional semisimple algebra A with unity, the multiplicative complexity C ( A ) of the multiplication in A is bounded from below by 5 2 dim A - 3 ( n 1 + ⋯ + n t ) if the decomposition of A ≅ A 1 × ⋯ × A t into simple algebras A τ ≅ D τ n τ × n τ contains only noncommutative factors, that is, the division algebra D τ is noncommutative or n τ ⩾ 2. We also deal with the complexity of multiplication in algebras with nonzero radical. We present an example that shows that our methods in the semisimple case cannot be applied directly to this problem. We exhibit lower bound techniques for C ( A ) that yield bounds still significantly above the Alder–Strassen bound. The main application is the lower bound C ( T n ( k ) ) ⩾ ( 2 1 8 - o ( 1 ) ) dim T n ( k ) for the multiplicative complexity of multiplication in the algebra T n ( k ) of upper triangular n × n -matrices.

SODA Conference 2004 Conference Paper

Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem

• Markus Bläser

SODA Conference 2003 Conference Paper

A new approximation algorithm for the asymmetric TSP with triangle inequality

• Markus Bläser

TCS Journal 2003 Journal Article

The complexity of bivariate power series arithmetic

• Markus Bläser

Inspired by Schönhage's discussion in the Proc. 11th Applied Algebra and Error Correcting Codes Conference (AAECC), Lecture Notes in Comput. Sci. , Springer, Berlin, Vol. 948, 1995 pp. 70, we study the multiplicative complexity of the multiplication, squaring, inversion, and division of bivariate power series modulo the “triangular” and “quadratic” ideals (X d+1, X d Y, X d−1 Y 2, …, Y d+1) and (X d+1, Y d+1), respectively. For multiplication, we obtain the lower bounds 5 4 d2−O(d) and 2 1 3 d2−O(d) for the triangular and quadratic case, respectively, opposed to the upper bounds 3 2 d2+O(d) and 3d 2+O(d). For squaring, we prove the lower bounds 7 8 d2−O(d) and 1 3 5 d2−O(d). As upper bounds, we have d 2+O(d) and 2 1 2 d2+O(d) for the triangular and quadratic case, respectively. Concerning inversion, the obtained lower bounds coincide with those of squaring. As upper bounds, we show 3 5 6 d2+O(d) and 8 1 3 d2+O(d), respectively. The lower bounds for division are those of multiplication. The upper bounds follow from combining the bounds for inversion and multiplication. All of the above lower bounds hold over arbitrary fields (in the case of multiplication and division) and over fields of characteristic distinct from two (in the case of squaring and inversion), respectively. All upper bounds are valid for fields that “support FFTs”, that is, fields that have characteristic zero and contain all roots of unity.

SODA Conference 2002 Conference Paper

An 8/13-approximation algorithm for the asymmetric maximum TSP

• Markus Bläser

TCS Journal 2002 Journal Article

Uniform computational complexity of the derivatives of C∞-functions

• Markus Bläser

We discuss the uniform computational complexity of the derivatives of C ∞-functions in the model of Ko and Friedman (Ko, Complexity Theory of Real Functions, Birkhäuser, Basel, 1991; Ko, Friedman, Theor. Comput. Sci. 20 (1982) 323–352). We construct a polynomial time computable real function g∈C ∞[−1, 1] such that the sequence {|g(n)(0)|}n∈N is not bounded by any recursive function. On the other hand, we show that if f∈C ∞[−1, 1] is polynomial time computable and the sequence of the derivatives of f is uniformly polynomially bounded, i. e. , |f (n)(x)| is bounded by 2 p(n) for all x∈[−1, 1] for some polynomial p, then the sequence {f(n)}n∈N is uniformly polynomial time computable.

MFCS Conference 2001 Conference Paper

Computing Reciprocals of Bivariate Power Series

• Markus Bläser

Abstract We consider the multiplicative complexity of the inversion and division of bivariate power series modulo the “triangular” ideal generated by all monomials of total degree n + 1. For inversion, we obtain a lower bound of 7/8 n 2 – O(n) opposed to an upper bound of 7/3 n 2 + O(n). The former bound holds for all fields with characteristic distinct from two while the latter is valid over fields of characteristic zero that contain all roots of unity (like e. g. ℂ ). Regarding division, we prove a lower bound of 5/4 n 2 – O(n) and an upper bound of 3 5/6 n 2 + O(n). Here, the former bound is proven for arbitrary fields whereas the latter bound holds for fields of characteristic zero that contain all roots of unity. Similar results are obtained for inversion and division modulo the “rectangular” ideal (X n +1, Y n +1 ).

FOCS Conference 1999 Conference Paper

A 5/2 n 2 -Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields

• Markus Bläser

We prove a lower bound of 5/2n/sup 2/-3n for the rank of n/spl times/n-matrix multiplication over an arbitrary field. Similar bounds hold for the rank of the multiplication in noncommutative division algebras and for the multiplication of upper triangular matrices.

FOCS Conference 1998 Conference Paper

Bivariate Polynomial Multiplication

• Markus Bläser

We study the multiplicative complexity and the rank of the multiplication in the local algebras R/sub m, n/=k[x, y]/(x/sup m+1/, y/sup n+1/) and T/sub n/=k[x, y]/(x/sup n+1/, x/sup n/y, .. ., y/sup n+1/) of bivariate polynomials. We obtain the lower bounds (21/3-0(1))/spl middot/dim R/sub m, n/, and (2 1/2 -0(1))/spl middot/dim T/sub n/ for the multiplicative complexity of the multiplication in R/sub m, n/ and T/sub n/, respectively. On the other hand, we derive the upper bounds 3/spl middot/dim T/sub n/-2n-2 and 3/spl middot/dim R/sub m. n/-m-n-3 for the rank of the multiplication in T/sub n/ and R/sub m, n/, respectively, provided that the ground field k admits "fast" univariate polynomial multiplication mod x/sup N/-1. Our results are also applicable to arbitrary finite dimensional algebras of truncated bivariate polynomials k[x, y]/I, where the ideal I=(x(d/sub 0/+1), x(d/sub 1/+1)y, .. ., x(d/sub n/+1)y/sup n/, y/sup n+1/) is described by a degree pattern d/sub 0//spl ges/d/sub 1//spl ges//spl middot//spl middot//spl middot//spl ges/d/sub n//spl ges/0.