Markus Bläser

Publication Activity (10 Years)

Years Active: 1998-2024
Publications (10 Years): 43

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

Computational Complexity Conference

MFCS

University of Bonn (PHD)

Education History

University of Bonn

PHD

Publications

Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz
Probabilistic and Causal Satisfiability: the Impact of Marginalization. CoRR (2024)
Markus Bläser, Julian Dörfler, Gorav Jindal
PosSLP and Sum of Squares. CoRR (2024)
Markus Bläser, Zhili Chen, Dung Hoang Duong, Antoine Joux, Tuong Ngoc Nguyen, Thomas Plantard, Youming Qiao, Willy Susilo, Gang Tang
On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures. PQCrypto (1) (2024)
Aaryan Gupta, Markus Bläser
Identification for Tree-Shaped Structural Causal Models in Polynomial Time. AAAI (2024)
Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, Saswata Mukherjee
Exponential Lower Bounds via Exponential Sums. ICALP (2024)
Markus Bläser, Julian Dörfler, Maciej Liskiewicz, Benito van der Zander
The Existential Theory of the Reals with Summation Operators. CoRR (2024)
Sanyam Agarwal, Markus Bläser
Probabilistic Generating Circuits - Demystified. CoRR (2024)
Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz
On the Complexity of Identification in Linear Structural Causal Models. CoRR (2024)
Benito van der Zander, Markus Bläser, Maciej Liskiewicz
The Hardness of Reasoning about Probabilities and Causality. IJCAI (2023)
Markus Bläser, Hendrik Mayer, Devansh Shringi
On the Multilinear Complexity of Associative Algebras. STACS (2023)
Benito van der Zander, Markus Bläser, Maciej Liskiewicz
The Hardness of Reasoning about Probabilities and Causality. CoRR (2023)
Markus Bläser
Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits. ICML (2023)
Aaryan Gupta, Markus Bläser
Identification for Tree-shaped Structural Causal Models in Polynomial Time. CoRR (2023)
Christophe Paul, Markus Bläser
Preface of STACS 2020 Special Issue. Theory Comput. Syst. 67 (1) (2023)
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). Dagstuhl Reports 12 (9) (2022)
Benito van der Zander, Marcel Wienöbst, Markus Bläser, Maciej Liskiewicz
Identification in Tree-shaped Linear Structural Causal Models. AISTATS (2022)
Benito van der Zander, Marcel Wienöbst, Markus Bläser, Maciej Liskiewicz
Identification in Tree-shaped Linear Structural Causal Models. CoRR (2022)
Markus Bläser, Julian Dörfler, Christian Ikenmeyer
On the Complexity of Evaluating Highest Weight Vectors. Computational Complexity Conference (2021)
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf Schreyer
On the Orbit Closure Containment Problem and Slice Rank of Tensors. SODA (2021)
Markus Bläser, Julian Dörfler, Christian Ikenmeyer
On the complexity of evaluating highest weight vectors. CoRR (2020)
Markus Bläser, Anurag Pandey
Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness. APPROX-RANDOM (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. CoRR (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Electron. Colloquium Comput. Complex. 27 (2020)
Markus Bläser, Vladimir Lysikov
Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras. MFCS (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Computational Complexity Conference (2020)
Markus Bläser, Christian Engels
Parameterized Valiant's Classes. CoRR (2019)
Markus Bläser, Christian Engels
Parameterized Valiant's Classes. IPEC (2019)
Vishwas Bhargava, Markus Bläser, Gorav Jindal, Anurag Pandey
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials. SODA (2019)
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf Schreyer
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory. CoRR (2019)
Markus Bläser, Gorav Jindal
On the Complexity of Symmetric Polynomials. ITCS (2019)
Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
Graph Pattern Polynomials. FSTTCS (2018)
Markus Bläser, Matthias Christandl, Jeroen Zuiddam
The border support rank of two-by-two matrix multiplication is seven. Chic. J. Theor. Comput. Sci. 2018 (2018)
Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
Graph Pattern Polynomials. CoRR (2018)
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov
Generalized matrix completion and algebraic natural proofs. STOC (2018)
Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). Dagstuhl Reports 8 (9) (2018)
Markus Bläser, Gorav Jindal, Anurag Pandey
A Deterministic PTAS for the Commutative Rank of Matrix Spaces. Theory Comput. 14 (1) (2018)
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov
Generalized Matrix Completion and Algebraic Natural Proofs. Electron. Colloquium Comput. Complex. 25 (2018)
Markus Bläser, Matthias Christandl, Jeroen Zuiddam
The border support rank of two-by-two matrix multiplication is seven. CoRR (2017)
Markus Bläser, Gorav Jindal, Anurag Pandey
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. Computational Complexity Conference (2017)
Markus Bläser, B. V. Raghavendra Rao, Jayalal Sarma
Testing Polynomial Equivalence by Scaling Matrices. FCT (2017)
Markus Bläser, Vladimir Lysikov
On degeneration of tensors and algebras. CoRR (2016)
Markus Bläser, Vladimir Lysikov
On Degeneration of Tensors and Algebras. MFCS (2016)
Markus Bläser, Gorav Jindal, Anurag Pandey
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. Electron. Colloquium Comput. Complex. 23 (2016)
Markus Bläser
Noncommutativity makes determinants hard. Inf. Comput. 243 (2015)
Markus Bläser, Bodo Manthey
Smoothed Complexity Theory. ACM Trans. Comput. Theory 7 (2) (2015)
Markus Bläser, Gorav Jindal
A new deterministic algorithm for sparse multivariate polynomial interpolation. ISSAC (2014)
Markus Bläser
Noncommutativity Makes Determinants Hard. ICALP (1) (2013)
Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. Algorithmica 66 (2) (2013)
Markus Bläser
Fast Matrix Multiplication. Theory Comput. 5 (2013)
Markus Bläser, Radu Curticapean
Weighted Counting of k-Matchings Is #W[1]-Hard. IPEC (2012)
Markus Bläser, Holger Dell, Mahmoud Fouz
Complexity and Approximability of the Cover Polynomial. Comput. Complex. 21 (3) (2012)
Markus Bläser
Noncommutativity makes determinants hard. Electron. Colloquium Comput. Complex. 19 (2012)
Markus Bläser, Bodo Manthey
Smoothed Complexity Theory CoRR (2012)
Markus Bläser, Bodo Manthey
Smoothed Complexity Theory. MFCS (2012)
Markus Bläser, Konstantinos Panagiotou, B. V. Raghavendra Rao
A Probabilistic Analysis of Christofides' Algorithm. SWAT (2012)
Markus Bläser, Bekhan Chokaev
Algebras of Minimal Multiplicative Complexity. Computational Complexity Conference (2012)
Markus Bläser, Christian Hoffmann
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. Algorithmica 61 (1) (2011)
Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. WADS (2011)
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Privacy in Non-private Environments. Theory Comput. Syst. 48 (1) (2011)
Markus Bläser, Christian Engels
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals. STACS (2011)
Markus Bläser, Radu Curticapean
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree. MFCS (2011)
Markus Bläser, Holger Dell, Johann A. Makowsky
Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions. Theory Comput. Syst. 46 (4) (2010)
Markus Bläser, Christian Hoffmann
Fast computation of interlace polynomials on graphs of bounded treewidth CoRR (2009)
Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi
Deterministically testing sparse polynomial identities of unbounded degree. Inf. Process. Lett. 109 (3) (2009)
Markus Bläser, Andreas Meyer de Voltaire
Semisimple algebras of almost minimal rank over the reals. Theor. Comput. Sci. 410 (50) (2009)
Markus Bläser, Christian Hoffmann
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. ESA (2009)
Markus Bläser, L. Shankar Ram, Maxim Sviridenko
Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems. Oper. Res. Lett. 37 (3) (2009)
Markus Bläser, Elias Vicari
Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity. SAGT (2008)
Markus Bläser, Christian Hoffmann
On the Complexity of the Interlace Polynomial. STACS (2008)
Markus Bläser, Thomas Heynen, Bodo Manthey
Adding cardinality constraints to integer programs with applications to maximum satisfiability. Inf. Process. Lett. 105 (5) (2008)
Markus Bläser, Bodo Manthey, Oliver Putz
Approximating Multi-criteria Max-TSP. ESA (2008)
Markus Bläser, Holger Dell, Johann A. Makowsky
Complexity of the Bollobás-Riordan Polynomial. CSR (2008)
Markus Bläser, Moritz Hardt, David Steurer
Asymptotically Optimal Hitting Sets Against Polynomials. ICALP (1) (2008)
Markus Bläser, L. Shankar Ram
Approximately Fair Cost Allocation in Metric Traveling Salesman Games. Theory Comput. Syst. 43 (1) (2008)
Markus Bläser, Bodo Manthey, Oliver Putz
Approximating Multi-Criteria Max-TSP CoRR (2008)
Markus Bläser
A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Trans. Algorithms 4 (4) (2008)
Markus Bläser, Andreas Meyer de Voltaire
Semisimple Algebras of Almost Minimal Rank over the Reals. MFCS (2007)
Markus Bläser, Christian Hoffmann
On the Complexity of the Interlace Polynomial CoRR (2007)
Markus Bläser, Holger Dell
Complexity of the Cover Polynomial. ICALP (2007)
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Private Computation: k-Connected versus 1-Connected Networks. J. Cryptol. 19 (3) (2006)
Markus Bläser, Bodo Manthey, Jirí Sgall
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algorithms 4 (4) (2006)
Markus Bläser, Bodo Manthey
Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One. Algorithmica 42 (2) (2005)
Markus Bläser
Beyond the Alder-Strassen bound. Theor. Comput. Sci. 331 (1) (2005)
Markus Bläser
On the number of multiplications needed to invert a monic power series over fields of characteristic two. J. Complex. 21 (4) (2005)
Markus Bläser, L. Shankar Ram
An Improved Approximation Algorithm for TSP with Distances One and Two. FCT (2005)
Markus Bläser, L. Shankar Ram, Maxim Sviridenko
Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems. WADS (2005)
Markus Bläser, L. Shankar Ram
Approximate Fair Cost Allocation in Metric Traveling Salesman Games. WAOA (2005)
Markus Bläser
Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem. SODA (2004)
Markus Bläser
A Complete Characterization of the Algebras of Minimal Bilinear Complexity. SIAM J. Comput. 34 (2) (2004)
Markus Bläser
A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One. APPROX-RANDOM (2004)
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Privacy in Non-private Environments. ASIACRYPT (2004)
Markus Bläser
An 8/13-approximation algorithm for the asymmetric maximum TSP. J. Algorithms 50 (1) (2004)
Markus Bläser
An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. ICALP (2003)
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Privacy in Non-Private Environments Electron. Colloquium Comput. Complex. (071) (2003)
Markus Bläser
A new approximation algorithm for the asymmetric TSP with triangle inequality. SODA (2003)
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey
Private Computation - k-connected versus 1-connected Networks Electron. Colloquium Comput. Complex. 10 (009) (2003)
Markus Bläser
Computing small partial coverings. Inf. Process. Lett. 85 (6) (2003)
Markus Bläser, Bodo Manthey
Budget balanced mechanisms for the multicast pricing problem with rates. EC (2003)
Markus Bläser
The complexity of bivariate power series arithmetic. Theor. Comput. Sci. 295 (2003)
Markus Bläser
Algebras of Minimal Rank over Arbitrary Fields. STACS (2003)

Markus Bläser.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Markus Bläser