default search action
Markus Bläser
Person information
- affiliation: Saarland University, Saarbrücken, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j32]Markus Bläser, Benjamin Monmege:
Preface of STACS 2021 Special Issue. Theory Comput. Syst. 68(4): 835-837 (2024) - [c61]Aaryan Gupta, Markus Bläser:
Identification for Tree-Shaped Structural Causal Models in Polynomial Time. AAAI 2024: 20404-20411 - [c60]Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, Saswata Mukherjee:
Exponential Lower Bounds via Exponential Sums. ICALP 2024: 24:1-24:20 - [c59]Sanyam Agarwal, Markus Bläser:
Probabilistic Generating Circuits - Demystified. ICML 2024 - [c58]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: 227-261 - [i27]Markus Bläser, Julian Dörfler, Gorav Jindal:
PosSLP and Sum of Squares. CoRR abs/2403.00115 (2024) - [i26]Sanyam Agarwal, Markus Bläser:
Probabilistic Generating Circuits - Demystified. CoRR abs/2404.02912 (2024) - [i25]Markus Bläser, Julian Dörfler, Maciej Liskiewicz, Benito van der Zander:
The Existential Theory of the Reals with Summation Operators. CoRR abs/2405.04697 (2024) - [i24]Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz:
Probabilistic and Causal Satisfiability: the Impact of Marginalization. CoRR abs/2405.07373 (2024) - [i23]Julian Dörfler, Benito van der Zander, Markus Bläser, Maciej Liskiewicz:
On the Complexity of Identification in Linear Structural Causal Models. CoRR abs/2407.12528 (2024) - 2023
- [j31]Christophe Paul, Markus Bläser:
Preface of STACS 2020 Special Issue. Theory Comput. Syst. 67(1): 1-3 (2023) - [c57]Markus Bläser:
Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits. ICML 2023: 2592-2602 - [c56]Benito van der Zander, Markus Bläser, Maciej Liskiewicz:
The Hardness of Reasoning about Probabilities and Causality. IJCAI 2023: 5730-5738 - [c55]Markus Bläser, Hendrik Mayer, Devansh Shringi
On the Multilinear Complexity of Associative Algebras. STACS 2023: 12:1-12:18 - [i22]Benito van der Zander, Markus Bläser, Maciej Liskiewicz:
The Hardness of Reasoning about Probabilities and Causality. CoRR abs/2305.09508 (2023) - [i21]Aaryan Gupta, Markus Bläser:
Identification for Tree-shaped Structural Causal Models in Polynomial Time. CoRR abs/2311.14058 (2023) - 2022
- [c54]Benito van der Zander, Marcel Wienöbst, Markus Bläser, Maciej Liskiewicz:
Identification in Tree-shaped Linear Structural Causal Models. AISTATS 2022: 6770-6792 - [i20]Benito van der Zander, Marcel Wienöbst, Markus Bläser, Maciej Liskiewicz:
Identification in Tree-shaped Linear Structural Causal Models. CoRR abs/2203.01852 (2022) - [i19]Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán:
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). Dagstuhl Reports 12(9): 41-59 (2022) - 2021
- [c53]Markus Bläser, Julian Dörfler
On the Complexity of Evaluating Highest Weight Vectors. CCC 2021: 29:1-29:36 - [c52]Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov
On the Orbit Closure Containment Problem and Slice Rank of Tensors. SODA 2021: 2565-2584 - [e2]Markus Bläser, Benjamin Monmege
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference). LIPIcs 187, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2021, ISBN 978-3-95977-180-1 [contents] - 2020
- [c51]Markus Bläser, Anurag Pandey:
Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness. APPROX-RANDOM 2020: 8:1-8:13 - [c50]Markus Bläser, Christian Ikenmeyer, Meena Mahajan
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. CCC 2020: 21:1-21:24 - [c49]Markus Bläser, Vladimir Lysikov
Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras. MFCS 2020: 17:1-17:15 - [e1]Christophe Paul
37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France. LIPIcs 154, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-140-5 [contents] - [i18]Markus Bläser, Julian Dörfler, Christian Ikenmeyer:
On the complexity of evaluating highest weight vectors. CoRR abs/2002.11594 (2020) - [i17]Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh:
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. CoRR abs/2003.04834 (2020) - [i16]Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh:
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [c48]Markus Bläser, Gorav Jindal
On the Complexity of Symmetric Polynomials. ITCS 2019: 47:1-47:14 - [c47]Markus Bläser, Christian Engels
Parameterized Valiant's Classes. IPEC 2019: 3:1-3:14 - [c46]Vishwas Bhargava
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials. SODA 2019: 647-661 - [i15]Markus Bläser, Christian Engels:
Parameterized Valiant's Classes. CoRR abs/1907.12287 (2019) - [i14]Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory. CoRR abs/1911.02534 (2019) - 2018
- [j30]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) - [j29]Markus Bläser, Gorav Jindal
A Deterministic PTAS for the Commutative Rank of Matrix Spaces. Theory Comput. 14(1): 1-21 (2018) - [c45]Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
Graph Pattern Polynomials. FSTTCS 2018: 18:1-18:13 - [c44]Markus Bläser, Christian Ikenmeyer, Gorav Jindal
Generalized matrix completion and algebraic natural proofs. STOC 2018: 1193-1206 - [i13]Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah:
Graph Pattern Polynomials. CoRR abs/1809.08858 (2018) - [i12]Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans:
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). Dagstuhl Reports 8(9): 133-153 (2018) - [i11]Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov:
Generalized Matrix Completion and Algebraic Natural Proofs. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c43]Markus Bläser, Gorav Jindal
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. CCC 2017: 33:1-33:16 - [c42]Markus Bläser, B. V. Raghavendra Rao
Testing Polynomial Equivalence by Scaling Matrices. FCT 2017: 111-122 - [i10]Markus Bläser, Matthias Christandl, Jeroen Zuiddam:
The border support rank of two-by-two matrix multiplication is seven. CoRR abs/1705.09652 (2017) - 2016
- [c41]Markus Bläser, Vladimir Lysikov
On Degeneration of Tensors and Algebras. MFCS 2016: 19:1-19:11 - [r2]Markus Bläser:
Metric TSP. Encyclopedia of Algorithms 2016: 1276-1279 - [i9]Markus Bläser, Vladimir Lysikov
On degeneration of tensors and algebras. CoRR abs/1606.04253 (2016) - [i8]Markus Bläser, Gorav Jindal, Anurag Pandey:
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j28]Markus Bläser:
Noncommutativity makes determinants hard. Inf. Comput. 243: 133-144 (2015) - [j27]Markus Bläser, Bodo Manthey:
Smoothed Complexity Theory. ACM Trans. Comput. Theory 7(2): 6:1-6:21 (2015) - 2014
- [c40]Markus Bläser, Gorav Jindal
A new deterministic algorithm for sparse multivariate polynomial interpolation. ISSAC 2014: 51-58 - 2013
- [j26]Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. Algorithmica 66(2): 397-418 (2013) - [j25]Markus Bläser:
Fast Matrix Multiplication. Theory Comput. 5: 1-60 (2013) - [c39]Markus Bläser:
Noncommutativity Makes Determinants Hard. ICALP (1) 2013: 172-183 - 2012
- [j24]Markus Bläser, Holger Dell
Complexity and Approximability of the Cover Polynomial. Comput. Complex. 21(3): 359-419 (2012) - [c38]Markus Bläser, Bekhan Chokaev:
Algebras of Minimal Multiplicative Complexity. CCC 2012: 224-234 - [c37]Markus Bläser, Radu Curticapean:
Weighted Counting of k-Matchings Is #W[1]-Hard. IPEC 2012: 171-181 - [c36]Markus Bläser, Bodo Manthey:
Smoothed Complexity Theory. MFCS 2012: 198-209 - [c35]Markus Bläser, Konstantinos Panagiotou, B. V. Raghavendra Rao
A Probabilistic Analysis of Christofides' Algorithm. SWAT 2012: 225-236 - [i7]Markus Bläser, Bodo Manthey:
Smoothed Complexity Theory. CoRR abs/1202.1936 (2012) - [i6]Markus Bläser:
Noncommutativity makes determinants hard. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j23]Markus Bläser, Christian Hoffmann:
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. Algorithmica 61(1): 3-35 (2011) - [j22]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-private Environments. Theory Comput. Syst. 48(1): 211-245 (2011) - [c34]Markus Bläser, Radu Curticapean:
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree. MFCS 2011: 96-107 - [c33]Markus Bläser, Christian Engels
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals. STACS 2011: 555-566 - [c32]Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals. WADS 2011: 110-121 - 2010
- [j21]Markus Bläser, Holger Dell
Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions. Theory Comput. Syst. 46(4): 690-706 (2010)
2000 – 2009
- 2009
- [j20]Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi:
Deterministically testing sparse polynomial identities of unbounded degree. Inf. Process. Lett. 109(3): 187-192 (2009) - [j19]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): 176-180 (2009) - [j18]Markus Bläser, Andreas Meyer de Voltaire:
Semisimple algebras of almost minimal rank over the reals. Theor. Comput. Sci. 410(50): 5202-5214 (2009) - [c31]Markus Bläser, Christian Hoffmann:
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. ESA 2009: 623-634 - [i5]Markus Bläser, Christian Hoffmann:
Fast computation of interlace polynomials on graphs of bounded treewidth. CoRR abs/0902.1693 (2009) - 2008
- [j17]Markus Bläser, Thomas Heynen, Bodo Manthey:
Adding cardinality constraints to integer programs with applications to maximum satisfiability. Inf. Process. Lett. 105(5): 194-198 (2008) - [j16]Markus Bläser, L. Shankar Ram:
Approximately Fair Cost Allocation in Metric Traveling Salesman Games. Theory Comput. Syst. 43(1): 19-37 (2008) - [j15]Markus Bläser:
A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Trans. Algorithms 4(4): 47:1-47:15 (2008) - [c30]Markus Bläser, Holger Dell, Johann A. Makowsky:
Complexity of the Bollobás-Riordan Polynomial. CSR 2008: 86-98 - [c29]Markus Bläser, Bodo Manthey, Oliver Putz:
Approximating Multi-criteria Max-TSP. ESA 2008: 185-197 - [c28]Markus Bläser, Moritz Hardt, David Steurer:
Asymptotically Optimal Hitting Sets Against Polynomials. ICALP (1) 2008: 345-356 - [c27]Markus Bläser, Elias Vicari:
Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity. SAGT 2008: 206-217 - [c26]Markus Bläser, Christian Hoffmann:
On the Complexity of the Interlace Polynomial. STACS 2008: 97-108 - [r1]Markus Bläser:
Metric TSP. Encyclopedia of Algorithms 2008 - [i4]Markus Bläser, Bodo Manthey, Oliver Putz:
Approximating Multi-Criteria Max-TSP. CoRR abs/0806.3668 (2008) - 2007
- [c25]Markus Bläser, Holger Dell:
Complexity of the Cover Polynomial. ICALP 2007: 801-812 - [c24]Markus Bläser, Andreas Meyer de Voltaire:
Semisimple Algebras of Almost Minimal Rank over the Reals. MFCS 2007: 669-680 - [i3]Markus Bläser, Christian Hoffmann:
On the Complexity of the Interlace Polynomial. CoRR abs/0707.4565 (2007) - 2006
- [j14]Markus Bläser, Bodo Manthey, Jirí Sgall
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algorithms 4(4): 623-632 (2006) - [j13]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Private Computation: k-Connected versus 1-Connected Networks. J. Cryptol. 19(3): 341-357 (2006) - 2005
- [j12]Markus Bläser, Bodo Manthey:
Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One. Algorithmica 42(2): 121-139 (2005) - [j11]Markus Bläser:
On the number of multiplications needed to invert a monic power series over fields of characteristic two. J. Complex. 21(4): 413-419 (2005) - [j10]Markus Bläser:
Beyond the Alder-Strassen bound. Theor. Comput. Sci. 331(1): 3-21 (2005) - [c23]Markus Bläser, L. Shankar Ram:
An Improved Approximation Algorithm for TSP with Distances One and Two. FCT 2005: 504-515 - [c22]Markus Bläser, L. Shankar Ram, Maxim Sviridenko:
Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems. WADS 2005: 350-359 - [c21]Markus Bläser, L. Shankar Ram:
Approximate Fair Cost Allocation in Metric Traveling Salesman Games. WAOA 2005: 82-95 - 2004
- [j9]Markus Bläser:
An 8/13-approximation algorithm for the asymmetric maximum TSP. J. Algorithms 50(1): 23-48 (2004) - [j8]Markus Bläser:
A Complete Characterization of the Algebras of Minimal Bilinear Complexity. SIAM J. Comput. 34(2): 277-298 (2004) - [c20]Markus Bläser:
A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One. APPROX-RANDOM 2004: 61-71 - [c19]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-private Environments. ASIACRYPT 2004: 137-151 - [c18]Markus Bläser:
Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem. SODA 2004: 625-626 - 2003
- [j7]Markus Bläser:
Computing small partial coverings. Inf. Process. Lett. 85(6): 327-331 (2003) - [j6]Markus Bläser:
On the complexity of the multiplication of matrices of small formats. J. Complex. 19(1): 43-60 (2003) - [j5]Markus Bläser:
The complexity of bivariate power series arithmetic. Theor. Comput. Sci. 295: 65-83 (2003) - [c17]Markus Bläser:
An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. ICALP 2003: 157-163 - [c16]Markus Bläser, Bodo Manthey:
Budget balanced mechanisms for the multicast pricing problem with rates. EC 2003: 194-195 - [c15]Markus Bläser:
A new approximation algorithm for the asymmetric TSP with triangle inequality. SODA 2003: 638-645 - [c14]Markus Bläser:
Algebras of Minimal Rank over Arbitrary Fields. STACS 2003: 403-414 - [i2]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Private Computation - k-connected versus 1-connected Networks. Electron. Colloquium Comput. Complex. TR03 (2003) - [i1]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-Private Environments. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j4]Markus Bläser:
On the Multiplicative Complexity of the Inversion and Division of Hamiltonian Quaternions. Found. Comput. Math. 2(2): 191-199 (2002) - [j3]Markus Bläser:
Uniform computational complexity of the derivatives of Cinfinity-functions. Theor. Comput. Sci. 284(2): 199-206 (2002) - [c13]Markus Bläser, Bodo Manthey:
Two Approximation Algorithms for 3-Cycle Covers. APPROX 2002: 40-50 - [c12]Markus Bläser:
Algebras of Minimal Rank over Perfect Fields. CCC 2002: 113-122 - [c11]Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Siebert:
Private Computation - k-Connected versus 1-Connected Networks. CRYPTO 2002: 194-209 - [c10]Markus Bläser, Bodo Manthey:
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint. ISAAC 2002: 187-198 - [c9]Markus Bläser:
An 8/13-approximation algorithm for the asymmetric maximum TSP. SODA 2002: 64-73 - 2001
- [c8]Markus Bläser:
Complete Problems for Valiant's Class of qp-Computable Families of Polynomials. COCOON 2001: 1-10 - [c7]Markus Bläser, Bodo Siebert:
Computing Cycle Covers without Short Cycles. ESA 2001: 368-379 - [c6]Markus Bläser:
Algebras of minimal rank: overview and recent developments. FotFS 2001: 33-46 - [c5]Markus Bläser:
Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical. ICALP 2001: 79-91 - [c4]Markus Bläser:
Computing Reciprocals of Bivariate Power Series. MFCS 2001: 186-197 - [c3]Markus Bläser:
A (5/2)n2-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication. STACS 2001: 99-109 - 2000
- [j2]Markus Bläser:
Lower bounds for the bilinear complexity of associative algebras. Comput. Complex. 9(2): 73-112 (2000)
1990 – 1999
- 1999
- [b1]Markus Bläser:
Untere Schranken für den Rang assoziativer Algebren. University of Bonn, 1999 - [j1]Markus Bläser:
Lower bounds for the multiplicative complexity of matrix multiplication. Comput. Complex. 8(3): 203-226 (1999) - [c2]Markus Bläser:
A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields. FOCS 1999: 45-50 - 1998
- [c1]Markus Bläser:
Bivariate Polynomial Multiplication. FOCS 1998: 186-191
Coauthor Index
Bodo Manthey
aka: Bodo Siebert
aka: Bodo Siebert
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 21:25 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: