Publications

Found 60 results
Author Title [ Type(Asc)] Year
Filters: Author is Marek Karpinski  [Clear All Filters]
Technical Report
Clausen, M., Dress A., Grabmeier J., & Karpinski M. (1989).  On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields.
Blömer, J., Kalfane M., Karpinski M., Karp R. M., Luby M., & Zuckerman D. (1995).  An XOR-Based Erasure-Resilient Coding Scheme.
Karpinski, M., & Macintyre A. (1995).  VC Dimension of Sigmoidal and General Pfaffian Neural Networks.
Karpinski, M., & Werther T. (1991).  VC Dimension and Sampling Complexity of Learning Sparse Polynomials and Rational Functions.
Karpinski, M., & Werther T. (1989).  VC Dimension and Learnability of Sparse Polynomials and Rational Functions.
Karpinski, M., & Rytter W. (1993).  On a Sublinear Time Parallel Construction of Optimal Binary Search Trees.
Bürgisser, P., Karpinski M., & Lickteig T. Michael (1991).  Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication.
Goldmann, M., & Karpinski M. (1994).  Simulating Threshold Circuits by Majority Circuits (Extended Version).
Goldmann, M., & Karpinski M. (1992).  Simulating Threshold Circuits by Majority Circuits.
Grigoriev, D. Yu., Karpinski M., & Odlyzko A. M. (1991).  Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis.
Bshouty, N. H., Hancock T. R., Hellerstein L., & Karpinski M. (1992).  Read-Once Threshold Formulas, Justifying Assignments, and Generic Tranformations.
Karpinski, M., & Verbeek R. (1992).  On Randomized Versus Deterministic Computation.
Grigoriev, D. Yu., & Karpinski M. (1996).  Randomized ?(n^2) Lower Bound for Knapsack.
Gasieniec, L., Karpinski M., Plandowski W., & Rytter W. (1996).  Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach.
Bürgisser, P., Karpinski M., & Lickteig T. Michael (1992).  On Randomized Algebraic Test Complexity.
Karpinski, M., & Zimmermann W. (1991).  Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms.
Ablayev, F., & Karpinski M. (1995).  On the Power of Randomized Branching Programs.
Karpinski, M. (1997).  Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems.
Arora, S., Karger D. R., & Karpinski M. (1995).  Polynomial Time Approximation Schemes for Dense Instances of $NP$-HardProblems.
W. de la Vega, F., & Karpinski M. (1997).  Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT.
Karpinski, M., & Macintyre A. (1995).  Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks.
Karpinski, M., Dahlhaus E., & Lingas A. (1989).  A Parallel Algorithm for Maximum Matching in Planar Graphs.
Dahlhaus, E., Hajnal P., & Karpinski M. (1989).  Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs.
Berman, P., Charikar M., & Karpinski M. (1997).  On-Line Load Balancing for Related Machines.
Karpinski, M., & Zelikovsky A. (1995).  New Approximation Algorithms for the Steiner Tree Problems.

Pages