Publications

Found 60 results
Author Title [ Type(Asc)] Year
Filters: Author is Marek Karpinski  [Clear All Filters]
Technical Report
Freivalds, R., & Karpinski M. (1994).  Lower Space Bounds for Randomized Computation.
Grigoriev, D. Yu., Karpinski M., & Vorobjov N. (1993).  Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees.
Grigoriev, D. Yu., & Karpinski M. (1993).  Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Decision Trees.
Grigoriev, D. Yu., Karpinski M., der Heide F. Meyer auf, & Smolensky R. (1995).  A Lower Bound for Randomized Algebraic Decision Trees.
Ablayev, F., & Karpinski M. (1997).  A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs.
Angluin, D., Hellerstein L., & Karpinski M. (1989).  Learning Read-Once Formulas with Queries.
Hellerstein, L., & Karpinski M. (1989).  Learning Read-Once Formulas Using Membership Queries.
Grigoriev, D. Yu., Karpinski M., & Singer M. F. (1990).  Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents.
Dahlhaus, E., Karpinski M., & Novick M. B. (1989).  Fast Parallel Algorithms for the Clique Separator Decomposition.
Grigoriev, D. Yu., Karpinski M., & Yao A. C. (1995).  An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX.
Karpinski, M., & Lhotzky B. (1991).  An (epsilon, delta)--Approximation Algorithm of the Number of Zeros for a Multilinear Polynomial over GF[q].
Dahlhaus, E., & Karpinski M. (1989).  An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO).
Dahlhaus, E., & Karpinski M. (1989).  An Efficient Parallel Algorithm for the 3MIS Problem.
Dahlhaus, E., Karpinski M., & Kelsen P. (1992).  An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3.
Karpinski, M., & Shparlinski I. (1994).  Efficient Approximation Algorithms for Sparse Polynomials over Finite Fields.
Gathen, J. von zur, Karpinski M., & Shparlinski I. (1994).  Counting Curves and Their Projections.
Karpinski, M., Larmore L. L., & Rytter W. (1996).  Correctness of Constructing Optimal Alphabetic Trees Revisited.
Ehrenfeucht, A., & Karpinski M. (1990).  The Computational Complexity of (XOR, AND)-Counting Problems.
Grigoriev, D. Yu., Karpinski M., & Singer M. F. (1991).  Computational Complexity of Sparse Rational Interpolation.
Dahlhaus, E., & Karpinski M. (1994).  On the Computational Complexity of Matching on Chordal and Strongly Chordal Graphs.
Hellerstein, L., & Karpinski M. (1991).  Computational Complexity of Learning Read-Once Formulas over Different Bases.
Karpinski, M., & Verbeek R. (1992).  Computation of the Additive Complexity of Algebraic Circuits with Root Extracting.
Berman, P., Karpinski M., Larmore L. L., Plandowski W., & Rytter W. (1996).  The Complexity of Two-Dimensional Compressed Pattern Matching.
Karpinski, M., & der Heide F. Meyer auf (1990).  On the Complexity of Genuinely Polynomial Computation.
Karpinski, M. (1989).  Boolean Circuit Complexity of Algebraic Interpolation Problems.

Pages