 | 2012 |
|---|
| 64 |       | Markus Bläser,
Bodo Manthey:
Smoothed Complexity Theory
CoRR abs/1202.1936: (2012) |
| 2011 |
|---|
| 63 | | Markus Bläser,
Radu Curticapean:
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree.
MFCS 2011: 96-107 |
| 62 | | Markus Bläser,
Christian Engels:
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals.
STACS 2011: 555-566 |
| 61 | | Markus Bläser,
Bodo Manthey,
B. V. Raghavendra Rao:
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals.
WADS 2011: 110-121 |
| 60 | | Markus Bläser,
Christian Hoffmann:
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
Algorithmica 61(1): 3-35 (2011) |
| 59 | | Markus Bläser,
Jean-Sébastien Coron,
Alexey Pospelov:
Small Private Circuits
CoRR abs/1112.1308: (2011) |
| 58 | | Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey:
Privacy in Non-private Environments.
Theory Comput. Syst. 48(1): 211-245 (2011) |
| 2010 |
|---|
| 57 | | Markus Bläser,
Holger Dell,
Johann A. Makowsky:
Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions.
Theory Comput. Syst. 46(4): 690-706 (2010) |
| 2009 |
|---|
| 56 | | Markus Bläser,
Christian Hoffmann:
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.
ESA 2009: 623-634 |
| 55 | | Markus Bläser,
Christian Hoffmann:
Fast computation of interlace polynomials on graphs of bounded treewidth
CoRR abs/0902.1693: (2009) |
| 54 | | Markus Bläser,
Moritz Hardt,
Richard J. Lipton,
Nisheeth K. Vishnoi:
Deterministically testing sparse polynomial identities of unbounded degree.
Inf. Process. Lett. 109(3): 187-192 (2009) |
| 53 | | Markus Bläser,
L. Shankar Ram,
Maxim Sviridenko:
Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems.
Oper. Res. Lett. 37(3): 176-180 (2009) |
| 52 | | Markus Bläser,
Andreas Meyer de Voltaire:
Semisimple algebras of almost minimal rank over the reals.
Theor. Comput. Sci. 410(50): 5202-5214 (2009) |
| 2008 |
|---|
| 51 | | Markus Bläser,
Holger Dell,
Johann A. Makowsky:
Complexity of the Bollobás-Riordan Polynomial.
CSR 2008: 86-98 |
| 50 | | Markus Bläser,
Bodo Manthey,
Oliver Putz:
Approximating Multi-criteria Max-TSP.
ESA 2008: 185-197 |
| 49 | | Markus Bläser,
Moritz Hardt,
David Steurer:
Asymptotically Optimal Hitting Sets Against Polynomials.
ICALP (1) 2008: 345-356 |
| 48 | | Markus Bläser,
Elias Vicari:
Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity.
SAGT 2008: 206-217 |
| 47 | | Markus Bläser,
Christian Hoffmann:
On the Complexity of the Interlace Polynomial.
STACS 2008: 97-108 |
| 46 | | Markus Bläser:
Metric TSP.
Encyclopedia of Algorithms 2008 |
| 45 | | Markus Bläser:
A new approximation algorithm for the asymmetric TSP with triangle inequality.
ACM Transactions on Algorithms 4(4): (2008) |
| 44 | | Markus Bläser,
Bodo Manthey,
Oliver Putz:
Approximating Multi-Criteria Max-TSP
CoRR abs/0806.3668: (2008) |
| 43 | | Markus Bläser,
Thomas Heynen,
Bodo Manthey:
Adding cardinality constraints to integer programs with applications to maximum satisfiability.
Inf. Process. Lett. 105(5): 194-198 (2008) |
| 42 | | Markus Bläser,
L. Shankar Ram:
Approximately Fair Cost Allocation in Metric Traveling Salesman Games.
Theory Comput. Syst. 43(1): 19-37 (2008) |
| 2007 |
|---|
| 41 | | Markus Bläser,
Holger Dell:
Complexity of the Cover Polynomial.
ICALP 2007: 801-812 |
| 40 | | Markus Bläser,
Andreas Meyer de Voltaire:
Semisimple Algebras of Almost Minimal Rank over the Reals.
MFCS 2007: 669-680 |
| 39 | | Markus Bläser,
Christian Hoffmann:
On the Complexity of the Interlace Polynomial
CoRR abs/0707.4565: (2007) |
| 2006 |
|---|
| 38 | | Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey:
Private Computation: k-Connected versus 1-Connected Networks.
J. Cryptology 19(3): 341-357 (2006) |
| 37 | | Markus Bläser,
Bodo Manthey,
Jiri Sgall:
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality.
J. Discrete Algorithms 4(4): 623-632 (2006) |
| 2005 |
|---|
| 36 | | Markus Bläser,
L. Shankar Ram:
An Improved Approximation Algorithm for TSP with Distances One and Two.
FCT 2005: 504-515 |
| 35 | | Markus Bläser,
L. Shankar Ram,
Maxim Sviridenko:
Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems.
WADS 2005: 350-359 |
| 34 | | Markus Bläser,
L. Shankar Ram:
Approximate Fair Cost Allocation in Metric Traveling Salesman Games.
WAOA 2005: 82-95 |
| 33 | | Markus Bläser,
Bodo Manthey:
Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One.
Algorithmica 42(2): 121-139 (2005) |
| 32 | | 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 (2005) |
| 31 | | Markus Bläser:
Beyond the Alder-Strassen bound.
Theor. Comput. Sci. 331(1): 3-21 (2005) |
| 2004 |
|---|
| 30 | | Markus Bläser:
A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One.
APPROX-RANDOM 2004: 61-71 |
| 29 | | Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey:
Privacy in Non-private Environments.
ASIACRYPT 2004: 137-151 |
| 28 | | Markus Bläser:
Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem.
SODA 2004: 625-626 |
| 27 | | Markus Bläser:
An 8/13-approximation algorithm for the asymmetric maximum TSP.
J. Algorithms 50(1): 23-48 (2004) |
| 26 | | Markus Bläser:
A Complete Characterization of the Algebras of Minimal Bilinear Complexity.
SIAM J. Comput. 34(2): 277-298 (2004) |
| 2003 |
|---|
| 25 | | Markus Bläser,
Bodo Manthey:
Budget balanced mechanisms for the multicast pricing problem with rates.
ACM Conference on Electronic Commerce 2003: 194-195 |
| 24 | | Markus Bläser:
An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality.
ICALP 2003: 157-163 |
| 23 | | Markus Bläser:
A new approximation algorithm for the asymmetric TSP with triangle inequality.
SODA 2003: 638-645 |
| 22 | | Markus Bläser:
Algebras of Minimal Rank over Arbitrary Fields.
STACS 2003: 403-414 |
| 21 | | Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey:
Private Computation - k-connected versus 1-connected Networks
Electronic Colloquium on Computational Complexity (ECCC) 10(009): (2003) |
| 20 | | Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey:
Privacy in Non-Private Environments
Electronic Colloquium on Computational Complexity (ECCC)(071): (2003) |
| 19 | | Markus Bläser:
Computing small partial coverings.
Inf. Process. Lett. 85(6): 327-331 (2003) |
| 18 | | Markus Bläser:
On the complexity of the multiplication of matrices of small formats.
J. Complexity 19(1): 43-60 (2003) |
| 17 | | Markus Bläser:
The complexity of bivariate power series arithmetic.
Theor. Comput. Sci. 295: 65-83 (2003) |
| 2002 |
|---|
| 16 | | Markus Bläser,
Bodo Manthey:
Two Approximation Algorithms for 3-Cycle Covers.
APPROX 2002: 40-50 |
| 15 | | Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Siebert:
Private Computation - k-Connected versus 1-Connected Networks.
CRYPTO 2002: 194-209 |
| 14 | | Markus Bläser:
Algebras of Minimal Rank over Perfect Fields.
IEEE Conference on Computational Complexity 2002: 113-122 |
| 13 | | Markus Bläser,
Bodo Manthey:
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint.
ISAAC 2002: 187-198 |
| 12 | | Markus Bläser:
An 8/13-approximation algorithm for the asymmetric maximum TSP.
SODA 2002: 64-73 |
| 11 | | Markus Bläser:
On the Multiplicative Complexity of the Inversion and Division of Hamiltonian Quaternions.
Foundations of Computational Mathematics 2(2): 191-199 (2002) |
| 10 | | Markus Bläser:
Uniform computational complexity of the derivatives of Cinfinity-functions.
Theor. Comput. Sci. 284(2): 199-206 (2002) |
| 2001 |
|---|
| 9 | | Markus Bläser:
Complete Problems for Valiant's Class of qp-Computable Families of Polynomials.
COCOON 2001: 1-10 |
| 8 | | Markus Bläser,
Bodo Siebert:
Computing Cycle Covers without Short Cycles.
ESA 2001: 368-379 |
| 7 | | Markus Bläser:
Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical.
ICALP 2001: 79-91 |
| 6 | | Markus Bläser:
Computing Reciprocals of Bivariate Power Series.
MFCS 2001: 186-197 |
| 5 | | Markus Bläser:
A (5/2)n2-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication.
STACS 2001: 99-109 |
| 2000 |
|---|
| 4 | | Markus Bläser:
Lower bounds for the bilinear complexity of associative algebras.
Computational Complexity 9(2): 73-112 (2000) |
| 1999 |
|---|
| 3 | | Markus Bläser:
A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields.
FOCS 1999: 45-50 |
| 2 | | Markus Bläser:
Lower bounds for the multiplicative complexity of matrix multiplication.
Computational Complexity 8(3): 203-226 (1999) |
| 1998 |
|---|
| 1 | | Markus Bläser:
Bivariate Polynomial Multiplication.
FOCS 1998: 186-191 |
Data released under the ODC-BY 1.0 license — See also our legal information page