Publications

Found 60 results
Author Title [ Type(Desc)] Year
Filters: Author is Marek Karpinski  [Clear All Filters]
Technical Report
Karpinski, M., & Zelikovsky A. (1995).  1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems.
Bshouty, N. H., Hancock T. R., Hellerstein L., & Karpinski M. (1993).  An Algorithm to Learn Read-Once Threshold Formulas, and Some Generic Transformations Between Learning Models (Revised Version).
Grigoriev, D. Yu., & Karpinski M. (1991).  Algorithms for Sparse Rational Interpolation.
Karpinski, M., & Rytter W. (1993).  An Alphabet-Independent Optimal Parallel Search for Three Dimensional Patterns.
Berman, P., Fößmeier U., Karpinski M., Kaufmann M., & Zelikovsky A. (1994).  Approaching the 5/4-Approximation for Rectilinear Steiner Trees.
Karpinski, M., & Zelikovsky A. (1996).  Approximating Dense Cases of Covering Problems.
Karpinski, M., & Luby M. (1990).  Approximating the Number of Solutions of a GF[2] Polynomial.
Karpinski, M., Wirtgen J., & Zelikovsky A. (1997).  An Approximation Algorithm for the Bandwidth Problem on Dense Graphs.
Grigoriev, D. Yu., & Karpinski M. (1991).  An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q].
Karpinski, M., & Wirtgen J. (1997).  On Approximation Hardness of the Bandwidth Problem.
Karpinski, M. (1989).  Boolean Circuit Complexity of Algebraic Interpolation Problems.
Karpinski, M., & der Heide F. Meyer auf (1990).  On the Complexity of Genuinely Polynomial Computation.
Berman, P., Karpinski M., Larmore L. L., Plandowski W., & Rytter W. (1996).  The Complexity of Two-Dimensional Compressed Pattern Matching.
Karpinski, M., & Verbeek R. (1992).  Computation of the Additive Complexity of Algebraic Circuits with Root Extracting.
Hellerstein, L., & Karpinski M. (1991).  Computational Complexity of Learning Read-Once Formulas over Different Bases.
Dahlhaus, E., & Karpinski M. (1994).  On the Computational Complexity of Matching on Chordal and Strongly Chordal Graphs.
Grigoriev, D. Yu., Karpinski M., & Singer M. F. (1991).  Computational Complexity of Sparse Rational Interpolation.
Ehrenfeucht, A., & Karpinski M. (1990).  The Computational Complexity of (XOR, AND)-Counting Problems.
Karpinski, M., Larmore L. L., & Rytter W. (1996).  Correctness of Constructing Optimal Alphabetic Trees Revisited.
Gathen, J. von zur, Karpinski M., & Shparlinski I. (1994).  Counting Curves and Their Projections.
Karpinski, M., & Shparlinski I. (1994).  Efficient Approximation Algorithms for Sparse Polynomials over Finite Fields.
Dahlhaus, E., Karpinski M., & Kelsen P. (1992).  An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3.
Dahlhaus, E., & Karpinski M. (1989).  An Efficient Parallel Algorithm for the 3MIS Problem.
Dahlhaus, E., & Karpinski M. (1989).  An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO).
Karpinski, M., & Lhotzky B. (1991).  An (epsilon, delta)--Approximation Algorithm of the Number of Zeros for a Multilinear Polynomial over GF[q].

Pages