Markus Bläser

According to our database1, Markus Bläser authored at least 74 papers between 1998 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory.
CoRR, 2019

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

2018
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

2017
Testing Polynomial Equivalence by Scaling Matrices.
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016
Metric TSP.
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

2015
Smoothed Complexity Theory.
TOCT, 2015

2014
A new deterministic algorithm for sparse multivariate polynomial interpolation.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2014

2013
Fast Matrix Multiplication.
Theory of Computing, Graduate Surveys, 2013

Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
Algorithmica, 2013

2012
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[1]-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

2011
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
Algorithmica, 2011

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

2010
Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions.
Theory Comput. Syst., 2010

2009
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
CoRR, 2009

2008
Metric TSP.
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

2007
Complexity of the Cover Polynomial.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
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

2005
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.
Algorithmica, 2005

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

2004
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

2003
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

2002
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

2001
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

2000
Lower bounds for the bilinear complexity of associative algebras.
Computational Complexity, 2000

1999
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

1998
Bivariate Polynomial Multiplication.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998


  Loading...