According to our database1, Markus Bläser authored at least 74 papers between 1998 and 2019.
Legend:Book In proceedings Article PhD thesis Other
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory.
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019
Parameterized Valiant's Classes.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019
On the Complexity of Symmetric Polynomials.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
A Deterministic PTAS for the Commutative Rank of Matrix Spaces.
Theory of Computing, 2018
Generalized Matrix Completion and Algebraic Natural Proofs.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391).
Dagstuhl Reports, 2018
The border support rank of two-by-two matrix multiplication is seven.
Chicago J. Theor. Comput. Sci., 2018
Graph Pattern Polynomials.
Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018
Testing Polynomial Equivalence by Scaling Matrices.
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017
Encyclopedia of Algorithms, 2016
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces.
Electronic Colloquium on Computational Complexity (ECCC), 2016
On Degeneration of Tensors and Algebras.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016
Smoothed Complexity Theory.
A new deterministic algorithm for sparse multivariate polynomial interpolation.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2014
Fast Matrix Multiplication.
Theory of Computing, Graduate Surveys, 2013
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
Noncommutativity makes determinants hard.
Electronic Colloquium on Computational Complexity (ECCC), 2012
Complexity and Approximability of the Cover Polynomial.
Computational Complexity, 2012
A Probabilistic Analysis of Christofides' Algorithm.
Proceedings of the Algorithm Theory - SWAT 2012, 2012
Weighted Counting of k-Matchings Is #W-Hard.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012
Algebras of Minimal Multiplicative Complexity.
Proceedings of the 27th Conference on Computational Complexity, 2012
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011
Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions.
Theory Comput. Syst., 2010
Semisimple algebras of almost minimal rank over the reals.
Theor. Comput. Sci., 2009
Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems.
Oper. Res. Lett., 2009
Deterministically testing sparse polynomial identities of unbounded degree.
Inf. Process. Lett., 2009
Fast computation of interlace polynomials on graphs of bounded treewidth
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008
A new approximation algorithm for the asymmetric TSP with triangle inequality.
ACM Trans. Algorithms, 2008
Approximately Fair Cost Allocation in Metric Traveling Salesman Games.
Theory Comput. Syst., 2008
Adding cardinality constraints to integer programs with applications to maximum satisfiability.
Inf. Process. Lett., 2008
On the Complexity of the Interlace Polynomial.
Proceedings of the STACS 2008, 2008
Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity.
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008
Asymptotically Optimal Hitting Sets Against Polynomials.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008
Approximating Multi-criteria Max-TSP.
Proceedings of the Algorithms, 2008
Complexity of the Bollobás-Riordan Polynomial.
Proceedings of the Computer Science, 2008
Complexity of the Cover Polynomial.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007
Private Computation: k-Connected versus 1-Connected Networks.
J. Cryptology, 2006
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality.
J. Discrete Algorithms, 2006
Beyond the Alder-Strassen bound.
Theor. Comput. Sci., 2005
On the number of multiplications needed to invert a monic power series over fields of characteristic two.
J. Complex., 2005
Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One.
Approximate Fair Cost Allocation in Metric Traveling Salesman Games.
Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005
An Improved Approximation Algorithm for TSP with Distances One and Two.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005
A Complete Characterization of the Algebras of Minimal Bilinear Complexity.
SIAM J. Comput., 2004
An 8/13-approximation algorithm for the asymmetric maximum TSP.
J. Algorithms, 2004
Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004
A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One.
Proceedings of the Approximation, 2004
The complexity of bivariate power series arithmetic.
Theor. Comput. Sci., 2003
On the complexity of the multiplication of matrices of small formats.
J. Complex., 2003
Computing small partial coverings.
Inf. Process. Lett., 2003
Privacy in Non-Private Environments
Electronic Colloquium on Computational Complexity (ECCC), 2003
Algebras of Minimal Rank over Arbitrary Fields.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003
Budget balanced mechanisms for the multicast pricing problem with rates.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003
An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003
Uniform computational complexity of the derivatives of Cinfinity-functions.
Theor. Comput. Sci., 2002
On the Multiplicative Complexity of the Inversion and Division of Hamiltonian Quaternions.
Foundations of Computational Mathematics, 2002
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002
Algebras of Minimal Rank over Perfect Fields.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002
Two Approximation Algorithms for 3-Cycle Covers.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002
A (5/2)n2-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication.
Proceedings of the STACS 2001, 2001
Computing Reciprocals of Bivariate Power Series.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001
Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001
Algebras of minimal rank: overview and recent developments.
Proceedings of the Classical and New Paradigms of Computation and their Complexity Hierarchies, 2001
Computing Cycle Covers without Short Cycles.
Proceedings of the Algorithms, 2001
Complete Problems for Valiant's Class of qp-Computable Families of Polynomials.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001
Lower bounds for the bilinear complexity of associative algebras.
Computational Complexity, 2000
Untere Schranken für den Rang assoziativer Algebren.
PhD thesis, 1999
Lower bounds for the multiplicative complexity of matrix multiplication.
Computational Complexity, 1999
A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
Bivariate Polynomial Multiplication.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998