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.
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 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 [J2] |
[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: [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 Coo-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.