Arrow Research search

Author name cluster

Markus Bläser

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

27 papers
2 author rows

Possible papers

27

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.

PDF Details

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.

Details

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.

Details

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.

Details

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.

PDF Details DOI

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.

PDF Details DOI

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.

Details

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.

Details

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.

PDF Details DOI

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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 ).

Details

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.

Details