Publications

Found 60 results
Author Title [ Type(Desc)] Year
Filters: Author is Marek Karpinski  [Clear All Filters]
Technical Report
Grigoriev, D. Yu., Karpinski M., & Yao A. C. (1995).  An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX.
Dahlhaus, E., Karpinski M., & Novick M. B. (1989).  Fast Parallel Algorithms for the Clique Separator Decomposition.
Grigoriev, D. Yu., Karpinski M., & Singer M. F. (1990).  Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents.
Hellerstein, L., & Karpinski M. (1989).  Learning Read-Once Formulas Using Membership Queries.
Angluin, D., Hellerstein L., & Karpinski M. (1989).  Learning Read-Once Formulas with Queries.
Ablayev, F., & Karpinski M. (1997).  A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs.
Grigoriev, D. Yu., Karpinski M., der Heide F. Meyer auf, & Smolensky R. (1995).  A Lower Bound for Randomized 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., & Vorobjov N. (1993).  Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees.
Freivalds, R., & Karpinski M. (1994).  Lower Space Bounds for Randomized Computation.
Karpinski, M., & Zelikovsky A. (1995).  New Approximation Algorithms for the Steiner Tree Problems.
Berman, P., Charikar M., & Karpinski M. (1997).  On-Line Load Balancing for Related Machines.
Dahlhaus, E., Hajnal P., & Karpinski M. (1989).  Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs.
Karpinski, M., Dahlhaus E., & Lingas A. (1989).  A Parallel Algorithm for Maximum Matching in Planar Graphs.
Karpinski, M., & Macintyre A. (1995).  Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks.
W. de la Vega, F., & Karpinski M. (1997).  Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT.
Arora, S., Karger D. R., & Karpinski M. (1995).  Polynomial Time Approximation Schemes for Dense Instances of $NP$-HardProblems.
Karpinski, M. (1997).  Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems.
Ablayev, F., & Karpinski M. (1995).  On the Power of Randomized Branching Programs.
Karpinski, M., & Zimmermann W. (1991).  Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms.
Bürgisser, P., Karpinski M., & Lickteig T. Michael (1992).  On Randomized Algebraic Test Complexity.
Gasieniec, L., Karpinski M., Plandowski W., & Rytter W. (1996).  Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach.
Grigoriev, D. Yu., & Karpinski M. (1996).  Randomized ?(n^2) Lower Bound for Knapsack.
Karpinski, M., & Verbeek R. (1992).  On Randomized Versus Deterministic Computation.
Bshouty, N. H., Hancock T. R., Hellerstein L., & Karpinski M. (1992).  Read-Once Threshold Formulas, Justifying Assignments, and Generic Tranformations.

Pages