Polynomial time approximation schemes for dense instances of NP-hard problems S Arora, D Karger, M Karpinski Proceedings of the twenty-seventh annual ACM symposium on Theory of ..., 1995 | 398 | 1995 |

An XOR-based erasure-resilient coding scheme J Bloemer, M Kalfane, R Karp, M Karpinski, M Luby, D Zuckerman | 313 | 1995 |

On some tighter inapproximability results P Berman, M Karpinski Automata, Languages and Programming, 200-209, 1999 | 290 | 1999 |

Resolution for quantified Boolean formulas HK Buning, M Karpinski, A Flogel Information and computation 117 (1), 12-18, 1995 | 249 | 1995 |

Learning read-once formulas with queries D Angluin, L Hellerstein, M Karpinski Journal of the ACM (JACM) 40 (1), 185-210, 1993 | 218 | 1993 |

New approximation algorithms for the Steiner tree problems M Karpinski, A Zelikovsky Journal of Combinatorial Optimization 1 (1), 47-65, 1997 | 172 | 1997 |

Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields DY Grigoriev, M Karpinski, MF Singer SIAM Journal on Computing 19 (6), 1059-1063, 1990 | 141 | 1990 |

1.375-approximation algorithm for sorting by reversals P Berman, S Hannenhalli, M Karpinski Algorithms—ESA 2002, 200-210, 2002 | 127 | 2002 |

Approximation schemes for clustering problems WF de la Vega, M Karpinski, C Kenyon, Y Rabani Proceedings of the thirty-fifth annual ACM symposium on Theory of computing ..., 2003 | 119 | 2003 |

Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks M Karpinski, A Macintyre Journal of Computer and System Sciences 54 (1), 169-176, 1997 | 117 | 1997 |

The matching problem for bipartite graphs with polynomially bounded permanents is in NC DY Grigoriev, M Karpinski Foundations of Computer Science, 1987., 28th Annual Symposium on, 166-172, 1987 | 116 | 1987 |

Polynomial bounds for VC dimension of sigmoidal neural networks M Karpinski, A Macintyre Proceedings of the twenty-seventh annual ACM symposium on Theory of ..., 1995 | 111 | 1995 |

Efficient algorithms for Lempel-Ziv encoding L Gasieniec, M Karpinski, W Plandowski, W Rytter Algorithm Theory—SWAT'96, 392-403, 1996 | 102 | 1996 |

On zero-testing and interpolation of< i> k</i>-sparse multivariate polynomials over finite fields M Clausen, A Dress, J Grabmeier, M Karpinski Theoretical Computer Science 84 (2), 151-164, 1991 | 94 | 1991 |

8/7-approximation algorithm for (1, 2)-TSP P Berman, M Karpinski Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete ..., 2006 | 87 | 2006 |

An efficient pattern-matching algorithm for strings with short descriptions M Karpinski, W Rytter, A Shinohara Nord. J. Comput. 4 (2), 172-186, 1997 | 76 | 1997 |

An exponential lower bound for depth 3 arithmetic circuits D Grigoriev, M Karpinski Proceedings of the thirtieth annual ACM symposium on Theory of computing ..., 1998 | 73 | 1998 |

Random sampling and approximation of MAX-CSPs N Alon, WF de la Vega, R Kannan, M Karpinski Journal of Computer and System Sciences 67 (2), 212-243, 2003 | 70 | 2003 |

Fast parallel algorithms for graph matching problems M Karpinski, W Rytter Clarendon Press, 1998 | 66 | 1998 |

Approximating dense cases of covering problems M Karpinski, A Zelikovsky Proceedings of the DIMACS Workshop on Network Design: Connectivity and ..., 1998 | 64 | 1998 |