Markus Bläser

139 papers A* 23A 18B 18Misc 2Journal 65Unranked 10
YearRankTypeTitle / Venue / Authors
2026 J jnl
Exponential lower bound via exponential sums.
CoRR
Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, Saswata Mukherjee
2026 A* conf
Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz.
SODA
Markus Bläser, Sagnik Dutta, Gorav Jindal
2025 A* conf
From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy.
ICLR
Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz
2025 A* conf
Probabilistic and Causal Satisfiability: Constraining the Model.
ICALP
Markus Bläser, Julian Dörfler, Maciej Liskiewicz, Benito van der Zander
2025 J jnl
Probabilistic and Causal Satisfiability: Constraining the Model.
CoRR
Markus Bläser, Julian Dörfler, Maciej Liskiewicz, Benito van der Zander
2025 J jnl
Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz.
CoRR
Markus Bläser, Sagnik Dutta, Gorav Jindal
2025 A* conf
The Limits of Tractable Marginalization.
ICML
Oliver Broadrick, Sanyam Agarwal, Guy Van den Broeck, Markus Bläser
2025 J jnl
The Limits of Tractable Marginalization.
CoRR
Oliver Broadrick, Sanyam Agarwal, Guy Van den Broeck, Markus Bläser
2025 B conf
Which Graph Motif Parameters Count?
MFCS
Markus Bläser, Radu Curticapean, Julian Dörfler, Christian Ikenmeyer
2025 J jnl
Which graph motif parameters count?
CoRR
Markus Bläser, Radu Curticapean, Julian Dörfler, Christian Ikenmeyer
2024 J jnl
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381).
Dagstuhl Reports
Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, Jacobo Torán, Kilian Rothmund
2024 A* conf
Exponential Lower Bounds via Exponential Sums.
ICALP
Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, Saswata Mukherjee
2024 A* conf
Identification for Tree-Shaped Structural Causal Models in Polynomial Time.
AAAI
Aaryan Gupta, Markus Bläser
2024 — conf
On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures.
PQCrypto (1)
Markus Bläser, Zhili Chen, Dung Hoang Duong, Antoine Joux, Tuong Ngoc Nguyen, Thomas Plantard, Youming Qiao, Willy Susilo, Gang Tang
2024 A* conf
On the Complexity of Identification in Linear Structural Causal Models.
NeurIPS
Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz
2024 J jnl
On the Complexity of Identification in Linear Structural Causal Models.
CoRR
Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz
2024 — conf
PosSLP and Sum of Squares.
FSTTCS
Markus Bläser, Julian Dörfler, Gorav Jindal
2024 J jnl
PosSLP and Sum of Squares.
CoRR
Markus Bläser, Julian Dörfler, Gorav Jindal
2024 J jnl
Preface of STACS 2021 Special Issue.
Theory Comput. Syst.
Markus Bläser, Benjamin Monmege
2024 A* conf
Probabilistic Generating Circuits - Demystified.
ICML
Sanyam Agarwal, Markus Bläser
2024 J jnl
Probabilistic Generating Circuits - Demystified.
CoRR
Sanyam Agarwal, Markus Bläser
2024 J jnl
Probabilistic and Causal Satisfiability: the Impact of Marginalization.
CoRR
Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz
2024 B conf
The Existential Theory of the Reals with Summation Operators.
ISAAC
Markus Bläser, Julian Dörfler, Maciej Liskiewicz, Benito van der Zander
2024 J jnl
The Existential Theory of the Reals with Summation Operators.
CoRR
Markus Bläser, Julian Dörfler, Maciej Liskiewicz, Benito van der Zander
2023 J jnl
Identification for Tree-shaped Structural Causal Models in Polynomial Time.
CoRR
Aaryan Gupta, Markus Bläser
2023 A* conf
Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits.
ICML
Markus Bläser
2023 A conf
On the Multilinear Complexity of Associative Algebras.
STACS
Markus Bläser, Hendrik Mayer, Devansh Shringi
2023 J jnl
Preface of STACS 2020 Special Issue.
Theory Comput. Syst.
Christophe Paul, Markus Bläser
2023 A* conf
The Hardness of Reasoning about Probabilities and Causality.
IJCAI
Benito van der Zander, Markus Bläser, Maciej Liskiewicz
2023 J jnl
The Hardness of Reasoning about Probabilities and Causality.
CoRR
Benito van der Zander, Markus Bläser, Maciej Liskiewicz
2022 J jnl
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371).
Dagstuhl Reports
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán
2022 A conf
Identification in Tree-shaped Linear Structural Causal Models.
AISTATS
Benito van der Zander, Marcel Wienöbst, Markus Bläser, Maciej Liskiewicz
2022 J jnl
Identification in Tree-shaped Linear Structural Causal Models.
CoRR
Benito van der Zander, Marcel Wienöbst, Markus Bläser, Maciej Liskiewicz
2021 A ed.
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, Saarbrücken, Germany (Virtual Conference), March 16-19, 2021
STACS
Markus Bläser, Benjamin Monmege
2021 A conf
On the Complexity of Evaluating Highest Weight Vectors.
CCC
Markus Bläser, Julian Dörfler, Christian Ikenmeyer
2021 A* conf
On the Orbit Closure Containment Problem and Slice Rank of Tensors.
SODA
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf Schreyer
2020 A ed.
37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, Montpellier, France, March 10-13, 2020
STACS
Christophe Paul, Markus Bläser
2020 A conf
Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
CCC
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
2020 J jnl
Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
CoRR
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
2020 J jnl
Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
Electron. Colloquium Comput. Complex.
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
2020 J jnl
On the complexity of evaluating highest weight vectors.
CoRR
Markus Bläser, Julian Dörfler, Christian Ikenmeyer
2020 — conf
Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness.
APPROX-RANDOM
Markus Bläser, Anurag Pandey
2020 B conf
Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras.
MFCS
Markus Bläser, Vladimir Lysikov
2019 A* conf
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials.
SODA
Vishwas Bhargava, Markus Bläser, Gorav Jindal, Anurag Pandey
2019 A conf
On the Complexity of Symmetric Polynomials.
ITCS
Markus Bläser, Gorav Jindal
2019 B conf
Parameterized Valiant's Classes.
IPEC
Markus Bläser, Christian Engels
2019 J jnl
Parameterized Valiant's Classes.
CoRR
Markus Bläser, Christian Engels
2019 J jnl
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory.
CoRR
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf Schreyer
2018 J jnl
A Deterministic PTAS for the Commutative Rank of Matrix Spaces.
Theory Comput.
Markus Bläser, Gorav Jindal, Anurag Pandey
2018 J jnl
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391).
Dagstuhl Reports
Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans
2018 J jnl
Generalized Matrix Completion and Algebraic Natural Proofs.
Electron. Colloquium Comput. Complex.
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov
2018 A* conf
Generalized matrix completion and algebraic natural proofs.
STOC
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov
2018 — conf
Graph Pattern Polynomials.
FSTTCS
Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
2018 J jnl
Graph Pattern Polynomials.
CoRR
Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
2018 J jnl
The border support rank of two-by-two matrix multiplication is seven.
Chic. J. Theor. Comput. Sci.
Markus Bläser, Matthias Christandl, Jeroen Zuiddam
2017 A conf
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces.
CCC
Markus Bläser, Gorav Jindal, Anurag Pandey
2017 B conf
Testing Polynomial Equivalence by Scaling Matrices.
FCT
Markus Bläser, B. V. Raghavendra Rao, Jayalal Sarma
2017 J jnl
The border support rank of two-by-two matrix multiplication is seven.
CoRR
Markus Bläser, Matthias Christandl, Jeroen Zuiddam
2016 J jnl
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces.
Electron. Colloquium Comput. Complex.
Markus Bläser, Gorav Jindal, Anurag Pandey
2016 — ch.
Metric TSP.
Encyclopedia of Algorithms
Markus Bläser
2016 B conf
On Degeneration of Tensors and Algebras.
MFCS
Markus Bläser, Vladimir Lysikov
2016 J jnl
On degeneration of tensors and algebras.
CoRR
Markus Bläser, Vladimir Lysikov
2015 J jnl
Noncommutativity makes determinants hard.
Inf. Comput.
Markus Bläser
2015 J jnl
Smoothed Complexity Theory.
ACM Trans. Comput. Theory
Markus Bläser, Bodo Manthey
2014 B conf
A new deterministic algorithm for sparse multivariate polynomial interpolation.
ISSAC
Markus Bläser, Gorav Jindal
2013 J jnl
Fast Matrix Multiplication.
Theory Comput.
Markus Bläser
2013 — conf
Noncommutativity Makes Determinants Hard.
ICALP (1)
Markus Bläser
2013 J jnl
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
Algorithmica
Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
2012 — conf
A Probabilistic Analysis of Christofides' Algorithm.
SWAT
Markus Bläser, Konstantinos Panagiotou, B. V. Raghavendra Rao
2012 A conf
Algebras of Minimal Multiplicative Complexity.
CCC
Markus Bläser, Bekhan Chokaev
2012 J jnl
Complexity and Approximability of the Cover Polynomial.
Comput. Complex.
Markus Bläser, Holger Dell, Mahmoud Fouz
2012 J jnl
Noncommutativity makes determinants hard.
Electron. Colloquium Comput. Complex.
Markus Bläser
2012 J jnl
Smoothed Complexity Theory
CoRR
Markus Bläser, Bodo Manthey
2012 B conf
Smoothed Complexity Theory.
MFCS
Markus Bläser, Bodo Manthey
2012 B conf
Weighted Counting of k-Matchings Is #W[1]-Hard.
IPEC
Markus Bläser, Radu Curticapean
2011 J jnl
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
Algorithmica
Markus Bläser, Christian Hoffmann
2011 J jnl
Privacy in Non-private Environments.
Theory Comput. Syst.
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
2011 A conf
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals.
STACS
Markus Bläser, Christian Engels
2011 B conf
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
WADS
Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
2011 B conf
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree.
MFCS
Markus Bläser, Radu Curticapean
2010 J jnl
Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions.
Theory Comput. Syst.
Markus Bläser, Holger Dell, Johann A. Makowsky
2009 J jnl
Deterministically testing sparse polynomial identities of unbounded degree.
Inf. Process. Lett.
Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi
2009 A conf
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
ESA
Markus Bläser, Christian Hoffmann
2009 J jnl
Fast computation of interlace polynomials on graphs of bounded treewidth
CoRR
Markus Bläser, Christian Hoffmann
2009 J jnl
Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems.
Oper. Res. Lett.
Markus Bläser, L. Shankar Ram, Maxim Sviridenko
2009 J jnl
Semisimple algebras of almost minimal rank over the reals.
Theor. Comput. Sci.
Markus Bläser, Andreas Meyer de Voltaire
2008 J jnl
A new approximation algorithm for the asymmetric TSP with triangle inequality.
ACM Trans. Algorithms
Markus Bläser
2008 J jnl
Adding cardinality constraints to integer programs with applications to maximum satisfiability.
Inf. Process. Lett.
Markus Bläser, Thomas Heynen, Bodo Manthey
2008 J jnl
Approximately Fair Cost Allocation in Metric Traveling Salesman Games.
Theory Comput. Syst.
Markus Bläser, L. Shankar Ram
2008 J jnl
Approximating Multi-Criteria Max-TSP
CoRR
Markus Bläser, Bodo Manthey, Oliver Putz
2008 A conf
Approximating Multi-criteria Max-TSP.
ESA
Markus Bläser, Bodo Manthey, Oliver Putz
2008 — conf
Asymptotically Optimal Hitting Sets Against Polynomials.
ICALP (1)
Markus Bläser, Moritz Hardt, David Steurer
2008 Misc conf
Complexity of the Bollobás-Riordan Polynomial.
CSR
Markus Bläser, Holger Dell, Johann A. Makowsky
2008 B conf
Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity.
SAGT
Markus Bläser, Elias Vicari
2008 — ch.
Metric TSP.
Encyclopedia of Algorithms
Markus Bläser
2008 A conf
On the Complexity of the Interlace Polynomial.
STACS
Markus Bläser, Christian Hoffmann
2007 A* conf
Complexity of the Cover Polynomial.
ICALP
Markus Bläser, Holger Dell
2007 J jnl
On the Complexity of the Interlace Polynomial
CoRR
Markus Bläser, Christian Hoffmann
2007 B conf
Semisimple Algebras of Almost Minimal Rank over the Reals.
MFCS
Markus Bläser, Andreas Meyer de Voltaire
2006 J jnl
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality.
J. Discrete Algorithms
Markus Bläser, Bodo Manthey, Jirí Sgall
2006 J jnl
Private Computation: k-Connected versus 1-Connected Networks.
J. Cryptol.
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
2005 B conf
An Improved Approximation Algorithm for TSP with Distances One and Two.
FCT
Markus Bläser, L. Shankar Ram
2005 B conf
Approximate Fair Cost Allocation in Metric Traveling Salesman Games.
WAOA
Markus Bläser, L. Shankar Ram
2005 J jnl
Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One.
Algorithmica
Markus Bläser, Bodo Manthey
2005 J jnl
Beyond the Alder-Strassen bound.
Theor. Comput. Sci.
Markus Bläser
2005 B conf
Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems.
WADS
Markus Bläser, L. Shankar Ram, Maxim Sviridenko
2005 J jnl
On the number of multiplications needed to invert a monic power series over fields of characteristic two.
J. Complex.
Markus Bläser
2004 — conf
A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One.
APPROX-RANDOM
Markus Bläser
2004 J jnl
A Complete Characterization of the Algebras of Minimal Bilinear Complexity.
SIAM J. Comput.
Markus Bläser
2004 J jnl
An 8/13-approximation algorithm for the asymmetric maximum TSP.
J. Algorithms
Markus Bläser
2004 A* conf
Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem.
SODA
Markus Bläser
2004 A conf
Privacy in Non-private Environments.
ASIACRYPT
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
2003 A* conf
A new approximation algorithm for the asymmetric TSP with triangle inequality.
SODA
Markus Bläser
2003 A conf
Algebras of Minimal Rank over Arbitrary Fields.
STACS
Markus Bläser
2003 A* conf
An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality.
ICALP
Markus Bläser
2003 A* conf
Budget balanced mechanisms for the multicast pricing problem with rates.
EC
Markus Bläser, Bodo Manthey
2003 J jnl
Computing small partial coverings.
Inf. Process. Lett.
Markus Bläser
2003 J jnl
On the complexity of the multiplication of matrices of small formats.
J. Complex.
Markus Bläser
2003 J jnl
Privacy in Non-Private Environments
Electron. Colloquium Comput. Complex.
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
2003 J jnl
Private Computation - k-connected versus 1-connected Networks
Electron. Colloquium Comput. Complex.
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
2003 J jnl
The complexity of bivariate power series arithmetic.
Theor. Comput. Sci.
Markus Bläser
2002 A conf
Algebras of Minimal Rank over Perfect Fields.
CCC
Markus Bläser
2002 A* conf
An 8/13-approximation algorithm for the asymmetric maximum TSP.
SODA
Markus Bläser
2002 B conf
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint.
ISAAC
Markus Bläser, Bodo Manthey
2002 J jnl
On the Multiplicative Complexity of the Inversion and Division of Hamiltonian Quaternions.
Found. Comput. Math.
Markus Bläser
2002 A* conf
Private Computation - k-Connected versus 1-Connected Networks.
CRYPTO
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Siebert
2002 — conf
Two Approximation Algorithms for 3-Cycle Covers.
APPROX
Markus Bläser, Bodo Manthey
2002 J jnl
Uniform computational complexity of the derivatives of C
Theor. Comput. Sci.
Markus Bläser
2001 A conf
A (5/2)n
STACS
Markus Bläser
2001 — conf
Algebras of minimal rank: overview and recent developments.
FotFS
Markus Bläser
2001 Misc conf
Complete Problems for Valiant's Class of qp-Computable Families of Polynomials.
COCOON
Markus Bläser
2001 A conf
Computing Cycle Covers without Short Cycles.
ESA
Markus Bläser, Bodo Siebert
2001 B conf
Computing Reciprocals of Bivariate Power Series.
MFCS
Markus Bläser
2001 A* conf
Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical.
ICALP
Markus Bläser
2000 J jnl
Lower bounds for the bilinear complexity of associative algebras.
Comput. Complex.
Markus Bläser
1999 A* conf
A 5/2 n
FOCS
Markus Bläser
1999 J jnl
Lower bounds for the multiplicative complexity of matrix multiplication.
Comput. Complex.
Markus Bläser
1999 — —
Untere Schranken für den Rang assoziativer Algebren.
Markus Bläser
1998 A* conf
Bivariate Polynomial Multiplication.
FOCS
Markus Bläser