People

Prof. Dr. Markus Bläser

Saarland Informatics Campus
Building E1 3, Room 412

T: +49 681 302 5501
F: +49 681 302 5576
E: mblaeser@cs.uni-saarland.de

Consultation hours: Whenever my office door is open.
Or make an appointment by email.

Publications

DBLP maintains a list of my publications better than I can.

Below is a list of older publications from the postscript age. Publications from 2006 or later are on the group’s web page. If you are interested in a paper not available for download, please contact me.

Refereed Conferences

[C1]	Markus Bläser: “Bivariate polynomial multiplication“. Proc. 39th Ann. IEEE Symp. on Foundations of Comput. Sci. (FOCS), 186-191, 1998. Journal version: “The complexity of bivariate power series arithmetic“. Theoret. Comput. Sci., 295(1-3): 65-83, 2003.
[C2]	Markus Bläser: “A 2.5 n2-lower bound for the rank of n x n-matrix multiplication over arbitrary fields“. Proc. 40th Ann. IEEE Symp. on Foundations of Comput. Sci. (FOCS), 45-50, 1999. Results are generalized in: “Lower bounds for the bilinear complexity of associative algebras“. Comput. Complexity, 9:73-112, 2000.
[C3]	Markus Bläser: “A 2.5 n2-lower bound for the multiplicative complexity of n x n-matrix multiplication“. Proc. 18th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), Lectures Notes in Comput. Sci. 2010, 99-110, 2001. Journal version: “Beyond the Alder Strassen bound“. Theoret. Comput. Sci., 331(1):3-21, 2005.
[C4]	Markus Bläser: “Improvements of the Alder-Strassen bound: algebras with nonzero radical“. Proc. 28th Int. Coll. on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci. 2076, 79-91, 2001. Journal version: „Beyond the Alder Strassen bound“. Theoret. Comput. Sci., 331(1):3-21, 2005.
[C5]	Markus Bläser: “Complete problems for Valiant’s class of qp-computable families of polynomials“. Proc. 7th Ann. Int. Computing and Combinatorics Conf. (COCOON), Lecture Notes in Comput. Sci. 2108, 1-10, 2001.
[C6]	Markus Bläser: “Computing reciprocals of bivariate power series“. Proc. 26th Int. Symp. on Mathematical Foundations of Comput. Sci. (MFCS), Lecture Notes in Comput. Sci. 2136, 186-197, 2001. Journal version: “The complexity of bivariate power series arithmetic“. Theoret. Comput. Sci., 295(1-3): 65-83, 2003
[C7]	Markus Bläser, Bodo Siebert: “Computing cycle covers without short cycles“. Proc. 9th Ann. European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 2161, 369-379, 2001.
[C8]	Markus Bläser: “An 8/13-approximation algorithm for the asymmetric maximum TSP“. Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 64-73, 2002. Journal version: “An 8/13-approximation algorithm for the maximum asymmetric TSP“. J. Algorithms, 50:23-48, 2004.
[C9]	Markus Bläser: “Algebras of minimal rank over perfect fields“. Proc. 17th Ann. IEEE Computational Complexity Conference (CCC), 113-122, 2002.
[C10]	Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Siebert: “Private Computation – k-connected versus 1-connected Networks“. Proc. 22nd Ann. Int. Cryptology Conf. (CRYPTO), Lecture Notes in Comput. Sci. 2442, 194-209, 2002. A more recent version is available as ECCC-Report TR03-009 Revision 1.
[C11]	Markus Bläser, Bodo Manthey: “Two approximation algorithms for 3-cycle covers“. Proc. 5th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Comput. Sci. 2462, 40-50, 2002.
[C12]	Markus Bläser, Bodo Manthey: “Improved approximation algorithms for Max-2SAT with cardinality constraint“. Proc. 13th Ann. Int. Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Comput. Sci. 2518, 187-198, 2002.
[C13]	Markus Bläser: “A new approximation algorithm for the asymmetric TSP with triangle inequality“. Proc. 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 639-647, 2003. The proceedings version contains an error which is corrected in the journal version: “A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality”. ACM Trans. on Algorithms, 4(4), 2008.
[C14]	Markus Bläser: “Algebras of minimal rank over arbitrary fields”. Proc. 19th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), Lectures Notes in Comput. Sci. 2607, 403-414, 2003.
[C15]	Markus Bläser, Bodo Manthey: “Budget balanced mechanisms for the multicast pricing problem with rates” Proc. 4th ACM Conf. on Electronic Commerce, 194-195, 2003. See [R1] for a full version.
[C16]	Markus Bläser: “An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality”. Proc. 30th Int. Coll. on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci. 2719, 157-163, 2003. Improved journal version: Markus Bläser, Bodo Manthey, Jiří Sgall: “An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality”. Journal of Discrete Algorithms (JDA), 4(4):623-632, 2006
[C17]	Markus Bläser: “Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem”. Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 618-619, 2004.
[C18]	Markus Bläser: “A 3/4 approximation algorithm for maximum asymmetric TSP with weights zero and one”. Proc. 7th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Comput. Sci. 3122, 61-71, 2004.
[C19]	Markus Bläser, L. Shankar Ram, Maxim Sviridenko: “Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems.”. Proc. 9th Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Comput. Sci. 3122, 350-359, 2005.
[C20]	Markus Bläser, L. Shankar Ram: “An improved approximation algorithm for TSP with distances one and two.”. Proc. 15th Int. Symp. on Fundamentals of Computation Theory (FCT), Lecture Notes in Comput. Sci. 3623, 504-515, 2005.

Theses

[T1]	Markus Bläser: „Untere Schranken für den Rang assoziativer Algebren“. Dissertation, Universität Bonn, 1999. (in German)
[T2]	Markus Bläser: „Approximationsalgorithmen für Graphüberdeckungsprobleme“. Habilitationsschrift, Universität zu Lübeck, 2002. (in German)

Research Reports

[R1]	Markus Bläser: „Budget Balanced Mechanisms for the Multicast Pricing Problem with Rates“. Technical Report SIIM-TR-A-03-02, Institute für Informatik und Mathematik, Universtität Lübeck, February 2003, revised June 2003.