| 2026 | ICALP | The Complexity of Bisimilarity and Model Checking in Finitary Diagrams. | Markus Blser, Sagnik Dutta, Samuel Okyay |
| 2026 | SODA | Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz. | Markus Blser, Sagnik Dutta, Gorav Jindal |
| 2025 | ICALP | Probabilistic and Causal Satisfiability: Constraining the Model. | Markus Blser, Julian Drfler, Maciej Liskiewicz, Benito van der Zander |
| 2025 | ICLR | From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy. | Julian Drfler, Benito van der Zander, Markus Blser, Maciej Liskiewicz |
| 2025 | ICML | The Limits of Tractable Marginalization. | Oliver Broadrick, Sanyam Agarwal, Guy Van den Broeck, Markus Blser |
| 2025 | MFCS | Which Graph Motif Parameters Count? | Markus Blser, Radu Curticapean, Julian Drfler, Christian Ikenmeyer |
| 2024 | AAAI | Identification for Tree-Shaped Structural Causal Models in Polynomial Time. | Aaryan Gupta, Markus Blser |
| 2024 | ICALP | Exponential Lower Bounds via Exponential Sums. | Somnath Bhattacharjee, Markus Blser, Pranjal Dutta, Saswata Mukherjee |
| 2024 | ICML | Probabilistic Generating Circuits - Demystified. | Sanyam Agarwal, Markus Blser |
| 2024 | ISAAC | The Existential Theory of the Reals with Summation Operators. | Markus Blser, Julian Drfler, Maciej Liskiewicz, Benito van der Zander |
| 2024 | PQCrypto | On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures. | Markus Blser, Zhili Chen, Dung Hoang Duong, Antoine Joux, Tuong Ngoc Nguyen, Thomas Plantard, Youming Qiao, Willy Susilo, Gang Tang |
| 2023 | ICML | Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits. | Markus Blser |
| 2023 | IJCAI | The Hardness of Reasoning about Probabilities and Causality. | Benito van der Zander, Markus Blser, Maciej Liskiewicz |
| 2023 | STACS | On the Multilinear Complexity of Associative Algebras. | Markus Blser, Hendrik Mayer, Devansh Shringi |
| 2022 | AISTATS | Identification in Tree-shaped Linear Structural Causal Models. | Benito van der Zander, Marcel Wienbst, Markus Blser, Maciej Liskiewicz |
| 2021 | SODA | On the Orbit Closure Containment Problem and Slice Rank of Tensors. | Markus Blser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf Schreyer |
| 2020 | MFCS | Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras. | Markus Blser, Vladimir Lysikov |
| 2019 | SODA | A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials. | Vishwas Bhargava, Markus Blser, Gorav Jindal, Anurag Pandey |
| 2018 | STOC | Generalized matrix completion and algebraic natural proofs. | Markus Blser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov |
| 2017 | FCT | Testing Polynomial Equivalence by Scaling Matrices. | Markus Blser, B. V. Raghavendra Rao, Jayalal Sarma |
| 2016 | MFCS | On Degeneration of Tensors and Algebras. | Markus Blser, Vladimir Lysikov |
| 2014 | ISSAC | A new deterministic algorithm for sparse multivariate polynomial interpolation. | Markus Blser, Gorav Jindal |
| 2013 | ICALP | Noncommutativity Makes Determinants Hard. | Markus Blser |
| 2012 | MFCS | Smoothed Complexity Theory. | Markus Blser, Bodo Manthey |
| 2011 | MFCS | The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree. | Markus Blser, Radu Curticapean |
| 2011 | STACS | Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals. | Markus Blser, Christian Engels |
| 2011 | WADS | Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. | Markus Blser, Bodo Manthey, B. V. Raghavendra Rao |
| 2009 | ESA | Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. | Markus Blser, Christian Hoffmann |
| 2008 | CSR | Complexity of the Bollobs-Riordan Polynomial. | Markus Blser, Holger Dell, Johann A. Makowsky |
| 2008 | ESA | Approximating Multi-criteria Max-TSP. | Markus Blser, Bodo Manthey, Oliver Putz |
| 2008 | ICALP | Asymptotically Optimal Hitting Sets Against Polynomials. | Markus Blser, Moritz Hardt, David Steurer |
| 2008 | STACS | On the Complexity of the Interlace Polynomial. | Markus Blser, Christian Hoffmann |
| 2008 | SAGT | Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity. | Markus Blser, Elias Vicari |
| 2007 | ICALP | Complexity of the Cover Polynomial. | Markus Blser, Holger Dell |
| 2007 | MFCS | Semisimple Algebras of Almost Minimal Rank over the Reals. | Markus Blser, Andreas Meyer de Voltaire |
| 2005 | FCT | An Improved Approximation Algorithm for TSP with Distances One and Two. | Markus Blser, L. Shankar Ram |
| 2005 | WADS | Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems. | Markus Blser, L. Shankar Ram, Maxim Sviridenko |
| 2005 | WAOA | Approximate Fair Cost Allocation in Metric Traveling Salesman Games. | Markus Blser, L. Shankar Ram |
| 2004 | ASIACRYPT | Privacy in Non-private Environments. | Markus Blser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey |
| 2004 | SODA | Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem. | Markus Blser |
| 2003 | ICALP | An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. | Markus Blser |
| 2003 | SODA | A new approximation algorithm for the asymmetric TSP with triangle inequality. | Markus Blser |
| 2003 | STACS | Algebras of Minimal Rank over Arbitrary Fields. | Markus Blser |
| 2002 | CRYPTO | Private Computation - k-Connected versus 1-Connected Networks. | Markus Blser, Andreas Jakoby, Maciej Liskiewicz, Bodo Siebert |
| 2002 | ISAAC | Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint. | Markus Blser, Bodo Manthey |
| 2002 | SODA | An 8/13-approximation algorithm for the asymmetric maximum TSP. | Markus Blser |
| 2001 | COCOON | Complete Problems for Valiant's Class of qp-Computable Families of Polynomials. | Markus Blser |
| 2001 | ESA | Computing Cycle Covers without Short Cycles. | Markus Blser, Bodo Siebert |
| 2001 | ICALP | Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical. | Markus Blser |
| 2001 | MFCS | Computing Reciprocals of Bivariate Power Series. | Markus Blser |
| 2001 | STACS | A (5/2)n | Markus Blser |
| 1999 | FOCS | A 5/2 n | Markus Blser |
| 1998 | FOCS | Bivariate Polynomial Multiplication. | Markus Blser |