Markus Bläser

Address:	Universität des Saarlandes Informatik Postfach 151150 66041 Saarbrücken Germany
Office:	Building E1 3, Room 412
Phone:	+49 681 302-5501
Fax:	+49 681 302-5576
Email:	"mblaeser" at "cs.uni-saarland.de"

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

Older Publications

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: [J5]
[C2]	Markus Bläser: "A 2.5 n²-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 [J2]
[C3]	Markus Bläser: "A 2.5 n²-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: [J9]
[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: [J9]
[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: [J5]
[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: [J8]
[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 [R6].
[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 [R7] 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.
[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.

Journals

[J1]	Markus Bläser: "Lower bounds for the multiplicative complexity of matrix multiplication". Comput. Complexity, 8:203-226, 1999.
[J2]	Markus Bläser: "Lower bounds for the bilinear complexity of associative algebras". Comput. Complexity, 9:73-112, 2000.
[J3]	Markus Bläser, Peter Kirrinnis, Daniel Lauer: "On the multiplicative complexity of the inversion and division of Hamiltonian quaternions". Found. Comput. Math., 2:191-199, 2002.
[J4]	Markus Bläser: "Uniform computational complexity of the derivatives of C^oo-functions". Theoret. Comput. Sci., 284(2):199-205, 2002.
[J5]	Markus Bläser: "The complexity of bivariate power series arithmetic". Theoret. Comput. Sci., 295(1-3): 65-83, 2003.
[J6]	Markus Bläser: "On the complexity of the multiplication of matrices of small formats". J. Complexity, 19:43-60, 2003.
[J7]	Markus Bläser: "Computing small partial coverings". Inform. Proc. Letters, 85(6):327-331, 2003.
[J8]	Markus Bläser: "An 8/13-approximation algorithm for the maximum asymmetric TSP". J. Algorithms, 50:23-48, 2004.
[J9]	Markus Bläser: "A complete characterization of the algebras of minimal bilinear complexity". SIAM J. Comput., 34(2):277-298, 2004.
[J10]	Markus Bläser: "Beyond the Alder Strassen bound.". Theoret. Comput. Sci., 331(1):3-21, 2005.
[J11]	Markus Bläser, Bodo Manthey: "Approximating maximum weight cycle covers in directed graphs with weights zero and one". Algorithmica, 42(2):121-139, 2005.
[J12]	Markus Bläser: "On the number of multiplications needed to invert a monic power series over fields of characteristic two". J. Complexity 21(4):413-419

Theses

[T1]	Markus Bläser: "Untere Schranken für den Rang assoziativer Algebren". Dissertation, Universität Bonn, 1999. (in German) [J2, J6] cover most of the material.
[T2]	Markus Bläser: "Approximationsalgorithmen für Graphüberdeckungsprobleme". Habilitationsschrift, Universität zu Lübeck, 2002. (in German) [C7, C8, C11, C13, C16, J7 ] cover most of the material.

Research Reports

[R1]	Markus Bläser: "On the number of multiplications needed to invert a monic power series over fields of characteristic two". Research Report, Institut für Informatik II, Universität Bonn, January 2000.
[R2]	Markus Bläser: "Searching for matrix multiplication algorithms by numerical minimization". Research Report, Institut für Informatik II, Universität Bonn, January 2000.
[R3]	Markus Bläser: "Algebras of minimal rank over perfect fields". Technical Report SIIM-TR-A-01-13, Institute für Informatik und Mathematik, Universtität Lübeck, August 2001.
[R4]	Markus Bläser: "An 8/13-approximation algorithm for the asymmetric maximum TSP". Technical Report SIIM-TR-A-01-21, Institute für Informatik und Mathematik, Universtität Lübeck, December 2001.
[R5]	Markus Bläser: "Algebras of minimal rank over arbitrary fields". Technical Report SIIM-TR-A-02-09, Institute für Informatik und Mathematik, Universtität Lübeck, May 2002.
[R6]	Markus Bläser: "A new approximation algorithm for the asymmetric TSP with triangle inequality". Technical Report SIIM-TR-A-02-20, Institute für Informatik und Mathematik, Universtität Lübeck, September 2002, revised December 2002.
[R7]	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.

© Copyright Notice:
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.