CV

Publications

Rhombus Criterion and the Chordal Graph Polytope (2023)

We define and study the Rhombus Criterion, a simple sufficient criterion to determine that two vertices does not span an edge of a polytope. For several well-known polytopes this is also a sufficient criterion, for example the CIM_G polytopes whenever G is a tree. We show that most pairs of vertices of the chordal graph polytope fulfill the rhombus criterion and conjecture that it is true for the rest. We ask whether it might be true for the CIM_n polytope as well. Using the rhombus criterion we are also able to compute the edge structure of the chordal graph polytope for n<7 and the edge structure of CIM_n when n<6. 

To appear on arxiv. 

Diameters of the Characteristic Imset Polytopes (2023) 

While edges of the characteristic imset polytpes are of interest, both for application and theory, computational data indicates that we only know of very few edges in general. Therefore we study the diameters of these polytopes, with the aim of obtaining a broader view of the problem. The diameter of a polytope is a worst case measure of how many steps any simplex-type algorithm must take. We show that the characteristic imset polytopes have low-degree polynomial bounds on the diameter, in p (the number of nodes of the DAGs). As the dimension grows exponentially in p, this indicates that these polytopes are rather connected and we can expect to have many edges. 

Arxiv version available here. 

On the Edges of Characteristic Imset Polytopes (2022)

To better understand the general edge structure of the polytope we describe the edge structure of faces with a clear combinatorial interpretation: for any undirected graph G we have the face CIM_G, the convex hull of the characteristic imsets of DAGs with skeleton G. We give a full edge-description of CIM_G whenever G is a tree, leading to interesting connections to other polytopes. In particular the well-studied stable set polytope can be recovered as a face of CIM_G when G is a tree. Building on this connection we are also able to give a description of all edges of CIM_G when G is a cycle, suggesting possible inroads for generalization. We then introduce an algorithm for learning directed trees from data, utilizing our newly discovered edges, that outperforms classical methods on  simulated Gaussian data. 

Arxiv version available here. 

Greedy Causal Discovery is Geometric (2021)

We show that small perturbations to DAGs that are used for causal discovery can be interpreted as edges the characteristic imset polytope CIM_p and that restrictions placed on the skeleton of the candidate DAGs correspond to faces of this polytope. Thus, we observe that GES, GIES, and MMHC all have geometric realizations as greedy edge-walks along CIM_p. Furthermore, the identified edges of CIM_p strictly generalize the moves of these algorithms. Exploiting this generalization, we introduce a greedy simplex-type algorithm called greedy CIM, and a hybrid variant, skeletal greedy CIM, that outperforms current competitors among hybrid and constraint-based algorithms.

SIAM journal of Discrete Mathematics 37(1), 2023, s. 233-252. Arxiv version available here. Code available at github.

LaserTank is NP-Complete (2019)

We prove that solving instances of the classic game LaserTank is NP-Complete.  

Lecture Notes in Computer Science, Springer , 2020, s. 333-338 (Conference Proceedings). Arxiv version available here.

Talks

Education

PhD-studies (KTH) 2018-now (80%)

Under the supervision of Svante Linusson and Liam Solus.

MSc in Mathematics (Uppsala University)

Master thesis advisor: Martin Herschend

Title: The Selfinjective Nakayama Algebras and their Complexity

Teaching

Teaching Assistant (KTH) 2018-now (20%)