The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Marek Karpinski: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Marek Karpinski, Angus Macintyre
    Approximating the Volume of General Pfaffian Bodies. [Citation Graph (2, 0)][DBLP]
    Structures in Logic and Computer Science, 1997, pp:162-173 [Conf]
  2. Dima Grigoriev, Marek Karpinski
    A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. [Citation Graph (0, 0)][DBLP]
    AAECC, 1993, pp:162-169 [Conf]
  3. Marek Karpinski, Igor Shparlinski
    On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials. [Citation Graph (0, 0)][DBLP]
    AAECC, 1999, pp:492-497 [Conf]
  4. Andris Ambainis, Kalvis Apsitis, Cristian Calude, Rusins Freivalds, Marek Karpinski, Tomas Larfeldt, Iveta Sala, Juris Smotrovs
    Effects of Kolmogorov Complexity Present in Inductive Inference as Well. [Citation Graph (0, 0)][DBLP]
    ALT, 1997, pp:244-259 [Conf]
  5. Rusins Freivalds, Dace Gobleja, Marek Karpinski, Carl H. Smith
    Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions. [Citation Graph (0, 0)][DBLP]
    AII/ALT, 1994, pp:100-105 [Conf]
  6. Marek Karpinski, Rutger Verbeek
    Randomness, Provability, and the Seperation of Monte Carlo Time and Space. [Citation Graph (0, 0)][DBLP]
    Computation Theory and Logic, 1987, pp:189-207 [Conf]
  7. Marek Karpinski
    On global word definability and constructively definable sets in Nn. [Citation Graph (0, 0)][DBLP]
    CAAP, 1980, pp:57-63 [Conf]
  8. Rusins Freivalds, Marek Karpinski, Carl H. Smith
    Co-Learning of Total Recursive Functions. [Citation Graph (0, 0)][DBLP]
    COLT, 1994, pp:190-197 [Conf]
  9. Lisa Hellerstein, Marek Karpinski
    Learning Read-Once Formulas Using Membership Queries. [Citation Graph (0, 0)][DBLP]
    COLT, 1989, pp:146-161 [Conf]
  10. Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter
    On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. [Citation Graph (0, 0)][DBLP]
    CPM, 1997, pp:40-51 [Conf]
  11. Marek Karpinski, Wojciech Rytter
    An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern. [Citation Graph (0, 0)][DBLP]
    CPM, 1994, pp:125-135 [Conf]
  12. Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter
    Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    CPM, 1996, pp:39-49 [Conf]
  13. Marek Karpinski, Wojciech Rytter, Ayumi Shinohara
    Pattern-Matching for Strings with Short Descriptions. [Citation Graph (0, 0)][DBLP]
    CPM, 1995, pp:205-214 [Conf]
  14. Andreas Flögel, Marek Karpinski, Hans Kleine Büning
    Subclasses of Quantified Boolean Formulas. [Citation Graph (0, 0)][DBLP]
    CSL, 1990, pp:145-155 [Conf]
  15. Marek Karpinski
    Boolean Complexity of Algebraic Interpolation Problems. [Citation Graph (0, 0)][DBLP]
    CSL, 1988, pp:138-147 [Conf]
  16. Marek Karpinski, Hans Kleine Büning, Peter H. Schmitt
    On the Computational Complexity of Quantified Horn Clauses. [Citation Graph (0, 0)][DBLP]
    CSL, 1987, pp:129-137 [Conf]
  17. Marek Karpinski, Yakov Nekrich
    Algorithms for Construction of Optimal and Almost-Optimal Length-Restricted Codes. [Citation Graph (0, 0)][DBLP]
    DCC, 2005, pp:464- [Conf]
  18. Piotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky
    Approaching the 5/4-Approximation for Rectilinear Steiner Trees. [Citation Graph (0, 0)][DBLP]
    ESA, 1994, pp:60-71 [Conf]
  19. Piotr Berman, Sridhar Hannenhalli, Marek Karpinski
    1.375-Approximation Algorithm for Sorting by Reversals. [Citation Graph (0, 0)][DBLP]
    ESA, 2002, pp:200-210 [Conf]
  20. Marek Karpinski, Yakov Nekrich
    Predecessor Queries in Constant Time?. [Citation Graph (0, 0)][DBLP]
    ESA, 2005, pp:238-248 [Conf]
  21. Marek Karpinski, Angus Macintyre
    Bounding VC-dimension of neural networks: Progress and prospects. [Citation Graph (0, 0)][DBLP]
    EuroCOLT, 1995, pp:337-341 [Conf]
  22. Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski
    On Computational Power of Quantum Branching Programs. [Citation Graph (0, 0)][DBLP]
    FCT, 2001, pp:59-70 [Conf]
  23. Magnus Bordewich, Martin E. Dyer, Marek Karpinski
    Path Coupling Using Stopping Times. [Citation Graph (0, 0)][DBLP]
    FCT, 2005, pp:19-31 [Conf]
  24. Ryszard Danecki, Marek Karpinski
    Decidability Results on Plane Automata Searching Mazes. [Citation Graph (0, 0)][DBLP]
    FCT, 1979, pp:84-91 [Conf]
  25. Marek Karpinski
    Approximating Bounded Degree Instances of NP-Hard Problems. [Citation Graph (0, 0)][DBLP]
    FCT, 2001, pp:24-34 [Conf]
  26. Marek Karpinski
    The Equivalences Problems for Binary EOL-Systems are Decidable. [Citation Graph (0, 0)][DBLP]
    FCT, 1977, pp:423-434 [Conf]
  27. Marek Karpinski
    Approximation Algorithms for Counting Problems in Finite Fields. [Citation Graph (0, 0)][DBLP]
    FCT, 1991, pp:45-46 [Conf]
  28. Marek Karpinski
    Randomized Complexity of Linear Arrangements and Polyhedra. [Citation Graph (0, 0)][DBLP]
    FCT, 1999, pp:1-12 [Conf]
  29. Elias Dahlhaus, Péter Hajnal, Marek Karpinski
    Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs [Citation Graph (0, 0)][DBLP]
    FOCS, 1988, pp:186-193 [Conf]
  30. Elias Dahlhaus, Marek Karpinski
    An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract) [Citation Graph (0, 0)][DBLP]
    FOCS, 1989, pp:454-459 [Conf]
  31. Dima Grigoriev, Marek Karpinski
    The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) [Citation Graph (0, 0)][DBLP]
    FOCS, 1987, pp:166-172 [Conf]
  32. Dima Grigoriev, Marek Karpinski
    An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] [Citation Graph (0, 0)][DBLP]
    FOCS, 1991, pp:662-669 [Conf]
  33. Dima Grigoriev, Marek Karpinski, Michael F. Singer
    Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents [Citation Graph (0, 0)][DBLP]
    FOCS, 1990, pp:840-846 [Conf]
  34. Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
    Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. [Citation Graph (0, 0)][DBLP]
    FOCS, 1995, pp:258-265 [Conf]
  35. Farid M. Ablayev, Marek Karpinski
    On the Power of Randomized Branching Programs. [Citation Graph (0, 0)][DBLP]
    ICALP, 1996, pp:348-356 [Conf]
  36. Piotr Berman, Marek Karpinski
    Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. [Citation Graph (0, 0)][DBLP]
    ICALP, 2002, pp:623-632 [Conf]
  37. Piotr Berman, Marek Karpinski
    On Some Tighter Inapproximability Results (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    ICALP, 1999, pp:200-209 [Conf]
  38. Piotr Berman, Marek Karpinski, Yakov Nekrich
    Approximating Huffman Codes in Parallel. [Citation Graph (0, 0)][DBLP]
    ICALP, 2002, pp:845-855 [Conf]
  39. Magnus Bordewich, Martin E. Dyer, Marek Karpinski
    Stopping Times, Metrics and Approximate Counting. [Citation Graph (0, 0)][DBLP]
    ICALP (1), 2006, pp:108-119 [Conf]
  40. Lars Engebretsen, Marek Karpinski
    Approximation Hardness of TSP with Bounded Metrics. [Citation Graph (0, 0)][DBLP]
    ICALP, 2001, pp:201-212 [Conf]
  41. Rusins Freivalds, Marek Karpinski
    Lower Space Bounds for Randomized Computation. [Citation Graph (0, 0)][DBLP]
    ICALP, 1994, pp:580-592 [Conf]
  42. Rusins Freivalds, Marek Karpinski
    Lower Time Bounds for Randomized Computation. [Citation Graph (0, 0)][DBLP]
    ICALP, 1995, pp:183-195 [Conf]
  43. Marek Karpinski, Rutger Verbeek
    On Randomized Versus Deterministic Computation. [Citation Graph (0, 0)][DBLP]
    ICALP, 1993, pp:227-240 [Conf]
  44. Marek Karpinski, Yakov Nekrich
    Optimal trade-off for merkle tree traversal. [Citation Graph (0, 0)][DBLP]
    ICETE, 2005, pp:275-282 [Conf]
  45. Cristina Bazgan, Marek Karpinski
    On the Complexity of Global Constraint Satisfaction. [Citation Graph (0, 0)][DBLP]
    ISAAC, 2005, pp:624-633 [Conf]
  46. Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas
    Embedding Point Sets into Plane Graphs of Small Dilation. [Citation Graph (0, 0)][DBLP]
    ISAAC, 2005, pp:5-16 [Conf]
  47. Marek Karpinski, Zbigniew W. Ras
    Learning Machine for Probabilistically Describable Concepts. [Citation Graph (0, 0)][DBLP]
    ISMIS, 1988, pp:353-362 [Conf]
  48. Alexander L. Chistov, Gábor Ivanyos, Marek Karpinski
    Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1997, pp:68-74 [Conf]
  49. Dima Grigoriev, Marek Karpinski
    Algorithms for Sparse Rational Interpolation. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1991, pp:7-13 [Conf]
  50. Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko
    Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. [Citation Graph (0, 0)][DBLP]
    ISSAC, 1992, pp:117-122 [Conf]
  51. Marek Karpinski
    Approximability of the Minimum Bisection Problem: An Algorithmic Challenge. [Citation Graph (0, 0)][DBLP]
    MFCS, 2002, pp:59-67 [Conf]
  52. Marek Karpinski
    Stretching by Probabilistic Tree Automata and Santos Grammars. [Citation Graph (0, 0)][DBLP]
    MFCS, 1974, pp:249-255 [Conf]
  53. Marek Karpinski
    Decision Algorithms for Havel's Branching Automata. [Citation Graph (0, 0)][DBLP]
    MFCS, 1975, pp:273-279 [Conf]
  54. Marek Karpinski
    Multiplicity Functions on Omega-Automata. [Citation Graph (0, 0)][DBLP]
    MFCS, 1976, pp:596-601 [Conf]
  55. Marek Karpinski, Friedhelm Meyer auf der Heide
    On the Complexity of Genuinely Polynomial Computation. [Citation Graph (0, 0)][DBLP]
    MFCS, 1990, pp:362-368 [Conf]
  56. Marek Karpinski, Wojciech Rytter
    On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. [Citation Graph (0, 0)][DBLP]
    MFCS, 1994, pp:453-461 [Conf]
  57. Andris Ambainis, Rusins Freivalds, Marek Karpinski
    Weak and Strong Recognition by 2-way Randomized Automata. [Citation Graph (0, 0)][DBLP]
    RANDOM, 1997, pp:175-185 [Conf]
  58. Marek Karpinski
    Polynominal Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. [Citation Graph (0, 0)][DBLP]
    RANDOM, 1997, pp:1-14 [Conf]
  59. Piotr Berman, Marek Karpinski
    Approximating minimum unsatisfiability of linear equations. [Citation Graph (0, 0)][DBLP]
    SODA, 2002, pp:514-516 [Conf]
  60. Piotr Berman, Marek Karpinski
    8/7-approximation algorithm for (1, 2)-TSP. [Citation Graph (0, 0)][DBLP]
    SODA, 2006, pp:641-648 [Conf]
  61. Béla Csaba, Marek Karpinski, Piotr Krysta
    Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. [Citation Graph (0, 0)][DBLP]
    SODA, 2002, pp:74-83 [Conf]
  62. Elias Dahlhaus, Marek Karpinski, Mark B. Novick
    Fast Parallel Algorithms for the Clique Separator Decomposition. [Citation Graph (0, 0)][DBLP]
    SODA, 1990, pp:244-251 [Conf]
  63. Marek Karpinski, Michael Luby
    Approximating the Number of Zeroes of a GF[2] Polynomial. [Citation Graph (0, 0)][DBLP]
    SODA, 1991, pp:300-303 [Conf]
  64. Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter
    Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees. [Citation Graph (0, 0)][DBLP]
    SODA, 1996, pp:36-41 [Conf]
  65. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon
    Approximation schemes for Metric Bisection and partitioning. [Citation Graph (0, 0)][DBLP]
    SODA, 2004, pp:506-515 [Conf]
  66. Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski
    Quantum Finite Multitape Automata. [Citation Graph (0, 0)][DBLP]
    SOFSEM, 1999, pp:340-348 [Conf]
  67. Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel
    Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. [Citation Graph (0, 0)][DBLP]
    STACS, 2001, pp:365-375 [Conf]
  68. Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
    Random sampling and approximation of MAX-CSP problems. [Citation Graph (0, 0)][DBLP]
    STOC, 2002, pp:232-239 [Conf]
  69. Sanjeev Arora, David R. Karger, Marek Karpinski
    Polynomial time approximation schemes for dense instances of NP-hard problems. [Citation Graph (0, 0)][DBLP]
    STOC, 1995, pp:284-293 [Conf]
  70. Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther
    On real Turing machines that toss coins. [Citation Graph (0, 0)][DBLP]
    STOC, 1995, pp:335-342 [Conf]
  71. Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski
    Counting curves and their projections. [Citation Graph (0, 0)][DBLP]
    STOC, 1993, pp:805-812 [Conf]
  72. Mikael Goldmann, Marek Karpinski
    Simulating threshold circuits by majority circuits. [Citation Graph (0, 0)][DBLP]
    STOC, 1993, pp:551-560 [Conf]
  73. Dima Grigoriev, Marek Karpinski
    Randomized Omega(n2) Lower Bound for Knapsack. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:76-85 [Conf]
  74. Dima Grigoriev, Marek Karpinski
    An Exponential Lower Bound for Depth 3 Arithmetic Circuits. [Citation Graph (0, 0)][DBLP]
    STOC, 1998, pp:577-582 [Conf]
  75. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
    A Lower Bound for Randomized Algebraic Decision Trees. [Citation Graph (0, 0)][DBLP]
    STOC, 1996, pp:612-619 [Conf]
  76. Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
    Lower bounds on testing membership to a polyhedron by algebraic decision trees. [Citation Graph (0, 0)][DBLP]
    STOC, 1994, pp:635-644 [Conf]
  77. Marek Karpinski, Angus Macintyre
    Polynomial bounds for VC dimension of sigmoidal neural networks. [Citation Graph (0, 0)][DBLP]
    STOC, 1995, pp:200-208 [Conf]
  78. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
    Approximation schemes for clustering problems. [Citation Graph (0, 0)][DBLP]
    STOC, 2003, pp:50-58 [Conf]
  79. Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala
    Tensor decomposition and approximation schemes for constraint satisfaction problems. [Citation Graph (0, 0)][DBLP]
    STOC, 2005, pp:747-754 [Conf]
  80. Elias Dahlhaus, Marek Karpinski
    A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    SWAT, 1988, pp:139-144 [Conf]
  81. Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
    Approximability of Dense Instances of NEAREST CODEWORD Problem. [Citation Graph (0, 0)][DBLP]
    SWAT, 2002, pp:298-307 [Conf]
  82. Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter
    Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    SWAT, 1996, pp:392-403 [Conf]
  83. Piotr Berman, Moses Charikar, Marek Karpinski
    On-line Load Balancing for Related Machines. [Citation Graph (0, 0)][DBLP]
    WADS, 1997, pp:116-125 [Conf]
  84. Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky
    Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem. [Citation Graph (0, 0)][DBLP]
    WADS, 2003, pp:401-411 [Conf]
  85. Marek Karpinski
    Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 2001, v:30, n:3, pp:386-397 [Journal]
  86. Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky
    Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 2005, v:42, n:2, pp:109-120 [Journal]
  87. Marek Karpinski
    Free Structure Tree Automata, II: Nondeterminstic and Deterministic Regularity. [Citation Graph (0, 0)][DBLP]
    Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys., 1973, v:21, n:5, pp:447-450 [Journal]
  88. Marek Karpinski
    Free Structure Tree Automata, III: Normalized Climbing Automata. [Citation Graph (0, 0)][DBLP]
    Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys., 1973, v:21, n:6, pp:567-572 [Journal]
  89. Marek Karpinski
    Free Structure Tree Automata IV. [Citation Graph (0, 0)][DBLP]
    Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys., 1974, v:22, n:, pp:87-91 [Journal]
  90. Marek Karpinski
    Probablistic Climbing and Sinking Languages. [Citation Graph (0, 0)][DBLP]
    Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys., 1974, v:22, n:, pp:1057-1062 [Journal]
  91. Marek Karpinski
    Valued Probabilistic Tree Functions. [Citation Graph (0, 0)][DBLP]
    Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys., 1976, v:24, n:, pp:927-930 [Journal]
  92. Peter Bürgisser, Marek Karpinski, Thomas Lickteig
    Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1991, v:1, n:, pp:131-155 [Journal]
  93. Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski
    Counting Curves and Their Projections. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1997, v:6, n:1, pp:64-99 [Journal]
  94. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
    A Lower Bound for Randomized Algebraic Decision Trees. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1997, v:6, n:4, pp:357-375 [Journal]
  95. Dima Grigoriev, Marek Karpinski, Roman Smolensky
    Randomization and the Computational Power of Analytic and Algebraic Decision Trees. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1997, v:6, n:4, pp:376-388 [Journal]
  96. Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao
    An exponential lower bound on the size of algebraic decision trees for Max. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1998, v:7, n:3, pp:193-203 [Journal]
  97. Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski
    An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 1994, v:4, n:, pp:37-61 [Journal]
  98. Elias Dahlhaus, Marek Karpinski
    Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs. [Citation Graph (0, 0)][DBLP]
    Discrete Applied Mathematics, 1998, v:84, n:1-3, pp:79-91 [Journal]
  99. Piotr Berman, Marek Karpinski, Alexander D. Scott
    Computational complexity of some restricted instances of 3-SAT. [Citation Graph (0, 0)][DBLP]
    Discrete Applied Mathematics, 2007, v:155, n:5, pp:649-653 [Journal]
  100. Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
    Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. [Citation Graph (0, 0)][DBLP]
    Discrete & Computational Geometry, 1997, v:17, n:2, pp:191-215 [Journal]
  101. Piotr Berman, Moses Charikar, Marek Karpinski
    On-Line Load Balancing for Related Machines [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:1, pp:- [Journal]
  102. Klaus Jansen, Marek Karpinski, Andrzej Lingas
    A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:64, pp:- [Journal]
  103. Lars Engebretsen, Marek Karpinski
    Approximation Hardness of TSP with Bounded Metrics [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:89, pp:- [Journal]
  104. Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
    Approximability of Dense Instances of NEAREST CODEWORD Problem [Citation Graph (0, 0)][DBLP]
    , 2000, v:7, n:91, pp:- [Journal]
  105. Uriel Feige, Marek Karpinski, Michael Langberg
    Improved Approximation of MAX-CUT on Graphs of Bounded Degree [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:21, pp:- [Journal]
  106. Uriel Feige, Marek Karpinski, Michael Langberg
    A Note on Approximating MAX-BISECTION on Regular Graphs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:43, pp:- [Journal]
  107. Piotr Berman, Marek Karpinski
    Approximating Minimum Unsatisfiability of Linear Equations [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:25, pp:- [Journal]
  108. Piotr Berman, Marek Karpinski
    Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:26, pp:- [Journal]
  109. Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas
    Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:51, pp:- [Journal]
  110. Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
    Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:34, pp:- [Journal]
  111. Marek Karpinski
    Approximating Bounded Degree Instances of NP-Hard Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:42, pp:- [Journal]
  112. Piotr Berman, Sridhar Hannenhalli, Marek Karpinski
    1.375-Approximation Algorithm for Sorting by Reversals [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:47, pp:- [Journal]
  113. Piotr Berman, Marek Karpinski
    Efficient Amplifiers and Bounded Degree Optimization [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:53, pp:- [Journal]
  114. Piotr Berman, Marek Karpinski
    Improved Approximations for General Minimum Cost Scheduling [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:097, pp:- [Journal]
  115. Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
    Random Sampling and Approximation of MAX-CSP Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:100, pp:- [Journal]
  116. Piotr Berman, Marek Karpinski, Yakov Nekrich
    Approximating Huffman Codes in Parallel [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:018, pp:- [Journal]
  117. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
    Polynomial Time Approximation Schemes for Metric Min-Sum Clustering [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:025, pp:- [Journal]
  118. Marek Karpinski, Yakov Nekrich
    Parallel Construction of Minimum Redundancy Length-Limited Codes [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:029, pp:- [Journal]
  119. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon
    A Polynomial Time Approximation Scheme for Metric MIN-BISECTION [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:041, pp:- [Journal]
  120. Wenceslas Fernandez de la Vega, Marek Karpinski
    A Polynomial Time Approximation Scheme for Subdense MAX-CUT [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:044, pp:- [Journal]
  121. Marek Karpinski
    On Approximability of Minimum Bisection Problem [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:046, pp:- [Journal]
  122. Wenceslas Fernandez de la Vega, Marek Karpinski
    9/8-Approximation Algorithm for Random MAX-3SAT [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:070, pp:- [Journal]
  123. Piotr Berman, Marek Karpinski
    Improved Approximation Lower Bounds on Small Occurrence Optimization [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2003, v:10, n:008, pp:- [Journal]
  124. Piotr Berman, Marek Karpinski, Alex D. Scott
    Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2003, v:10, n:022, pp:- [Journal]
  125. Piotr Berman, Marek Karpinski, Alex D. Scott
    Approximation Hardness of Short Symmetric Instances of MAX-3SAT [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2003, v:, n:049, pp:- [Journal]
  126. Piotr Berman, Marek Karpinski
    Approximability of Hypergraph Minimum Bisection [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2003, v:, n:056, pp:- [Journal]
  127. Piotr Berman, Marek Karpinski, Yakov Nekrich
    Optimal Trade-Off for Merkle Tree Traversal [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:049, pp:- [Journal]
  128. Piotr Berman, Marek Karpinski, Alexander D. Scott
    Computational Complexity of Some Restricted Instances of 3SAT [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:111, pp:- [Journal]
  129. Marek Karpinski, Yakov Nekrich
    A Note on Traversing Skew Merkle Trees [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:118, pp:- [Journal]
  130. Magnus Bordewich, Martin E. Dyer, Marek Karpinski
    Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:002, pp:- [Journal]
  131. Piotr Berman, Marek Karpinski
    8/7-Approximation Algorithm for (1,2)-TSP [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:069, pp:- [Journal]
  132. Magnus Bordewich, Martin E. Dyer, Marek Karpinski
    Metric Construction, Stopping Times and Path Coupling. [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:151, pp:- [Journal]
  133. Marek Karpinski, Angus Macintyre
    Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1994, v:1, n:24, pp:- [Journal]
  134. Marek Karpinski, Alexander Zelikovsky
    1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:3, pp:- [Journal]
  135. Marek Karpinski, Wojciech RytterAyumi Shinohara
    Pattern-Matching for Strings with Short Descriptions [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:22, pp:- [Journal]
  136. Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao
    An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:57, pp:- [Journal]
  137. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
    A Lower Bound for Randomized Algebraic Decision Trees [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1995, v:2, n:63, pp:- [Journal]
  138. Marek Karpinski, Alexander Zelikovsky
    Approximating Dense Cases of Covering Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1997, v:4, n:4, pp:- [Journal]
  139. Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky
    An Approximation Algorithm for the Bandwidth Problem on Dense Graphs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1997, v:4, n:17, pp:- [Journal]
  140. Marek Karpinski
    Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1997, v:4, n:24, pp:- [Journal]
  141. Gunter Blache, Marek Karpinski, Juergen Wirtgen
    On Approximation Intractability of the Bandwidth Problem [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:14, pp:- [Journal]
  142. Wenceslas Fernandez de la Vega, Marek Karpinski
    On Approximation Hardness of Dense TSP and other Path Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:24, pp:- [Journal]
  143. Marek Karpinski
    On the Computational Power of Randomized Branching Programs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:38, pp:- [Journal]
  144. Wenceslas Fernandez de la Vega, Marek Karpinski
    Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:64, pp:- [Journal]
  145. Marek Karpinski
    Randomized Complexity of Linear Arrangements and Polyhedra [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1999, v:6, n:20, pp:- [Journal]
  146. Marek Karpinski, Igor Shparlinski
    On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1999, v:6, n:27, pp:- [Journal]
  147. Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko
    Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. [Citation Graph (0, 0)][DBLP]
    Fundam. Inform., 1996, v:28, n:3-4, pp:297-301 [Journal]
  148. Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas
    Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs. [Citation Graph (0, 0)][DBLP]
    Fundam. Inform., 2004, v:62, n:3-4, pp:369-375 [Journal]
  149. Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Christopher Pollett
    On the computational power of probabilistic and quantum branching program. [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 2005, v:203, n:2, pp:145-162 [Journal]
  150. Farid M. Ablayev, Marek Karpinski
    A lower bound for integer multiplication on randomized ordered read-once branching programs. [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 2003, v:186, n:1, pp:78-89 [Journal]
  151. Hans Kleine Büning, Marek Karpinski, Andreas Flögel
    Resolution for Quantified Boolean Formulas [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 1995, v:117, n:1, pp:12-18 [Journal]
  152. Rusins Freivalds, Marek Karpinski, Carl H. Smith, Rolf Wiehagen
    Learning by the Process of Elimination. [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 2002, v:176, n:1, pp:37-50 [Journal]
  153. Marek Karpinski, Jan van Leeuwen
    Preface [Citation Graph (0, 0)][DBLP]
    Information and Control, 1985, v:64, n:1-3, pp:1- [Journal]
  154. Marek Karpinski, Rutger Verbeek
    There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator [Citation Graph (0, 0)][DBLP]
    Information and Control, 1985, v:67, n:1-3, pp:158-162 [Journal]
  155. Marek Karpinski, Rutger Verbeek
    On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation [Citation Graph (0, 0)][DBLP]
    Information and Control, 1986, v:71, n:1/2, pp:131-142 [Journal]
  156. Marek Karpinski, Rutger Verbeek
    On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 1987, v:75, n:2, pp:178-189 [Journal]
  157. Susanne Albers, Marek Karpinski
    Randomized splay trees: Theoretical and experimental results. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 2002, v:81, n:4, pp:213-221 [Journal]
  158. Elias Dahlhaus, Marek Karpinski, Pierre Kelsen
    An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1992, v:42, n:6, pp:309-313 [Journal]
  159. Uriel Feige, Marek Karpinski, Michael Langberg
    A note on approximating Max-Bisection on regular graphs. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 2001, v:79, n:4, pp:181-188 [Journal]
  160. Andrzej Lingas, Marek Karpinski
    Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1989, v:30, n:1, pp:27-32 [Journal]
  161. Wenceslas Fernandez de la Vega, Marek Karpinski
    On the Approximation Hardness of Dense TSP and Other Path Problems. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1999, v:70, n:2, pp:53-55 [Journal]
  162. Dana Angluin, Lisa Hellerstein, Marek Karpinski
    Learning Read-Once Formulas with Queries. [Citation Graph (0, 0)][DBLP]
    J. ACM, 1993, v:40, n:1, pp:185-210 [Journal]
  163. Piotr Berman, Moses Charikar, Marek Karpinski
    On-Line Load Balancing for Related Machines. [Citation Graph (0, 0)][DBLP]
    J. Algorithms, 2000, v:35, n:1, pp:108-121 [Journal]
  164. Elias Dahlhaus, Péter Hajnal, Marek Karpinski
    On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs. [Citation Graph (0, 0)][DBLP]
    J. Algorithms, 1993, v:15, n:3, pp:367-384 [Journal]
  165. Uriel Feige, Marek Karpinski, Michael Langberg
    Improved approximation of Max-Cut on graphs of bounded degree. [Citation Graph (0, 0)][DBLP]
    J. Algorithms, 2002, v:43, n:2, pp:201-219 [Journal]
  166. Marek Karpinski, Michael Luby
    Approximating the Number of Zeroes of a GF[2] Polynomial. [Citation Graph (0, 0)][DBLP]
    J. Algorithms, 1993, v:14, n:2, pp:280-287 [Journal]
  167. Peter Bürgisser, Marek Karpinski, Thomas Lickteig
    On Randomized Semi-algebraic Test Complexity. [Citation Graph (0, 0)][DBLP]
    J. Complexity, 1993, v:9, n:2, pp:231-251 [Journal]
  168. Marek Karpinski, Alexander Zelikovsky
    New Approximation Algorithms for the Steiner Tree Problems. [Citation Graph (0, 0)][DBLP]
    J. Comb. Optim., 1997, v:1, n:1, pp:47-65 [Journal]
  169. Sanjeev Arora, David R. Karger, Marek Karpinski
    Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1999, v:58, n:1, pp:193-210 [Journal]
  170. Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
    Random sampling and approximation of MAX-CSPs. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2003, v:67, n:2, pp:212-243 [Journal]
  171. Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter
    On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2002, v:65, n:2, pp:332-350 [Journal]
  172. Elias Dahlhaus, Marek Karpinski
    Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1992, v:44, n:1, pp:94-102 [Journal]
  173. Lars Engebretsen, Marek Karpinski
    TSP with bounded metrics. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2006, v:72, n:4, pp:509-546 [Journal]
  174. Marek Karpinski, Angus Macintyre
    Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 1997, v:54, n:1, pp:169-176 [Journal]
  175. Marek Karpinski, Wojciech Rytter, Ayumi Shinohara
    An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions. [Citation Graph (0, 0)][DBLP]
    Nord. J. Comput., 1997, v:4, n:2, pp:172-186 [Journal]
  176. Marek Karpinski, Lawrence L. Larmore, Yakov Nekrich
    Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes. [Citation Graph (0, 0)][DBLP]
    Parallel Processing Letters, 2004, v:14, n:1, pp:99-105 [Journal]
  177. Marek Karpinski, Yakov Nekrich
    Algorithms for Construction of Optimal and Almost-optimal Length-restricted Codes. [Citation Graph (0, 0)][DBLP]
    Parallel Processing Letters, 2006, v:16, n:1, pp:81-92 [Journal]
  178. Marek Karpinski, Wojciech Rytter
    On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. [Citation Graph (0, 0)][DBLP]
    Parallel Processing Letters, 1998, v:8, n:3, pp:387-397 [Journal]
  179. Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
    Polynomial time approximation schemes for dense instances of minimum constraint satisfaction. [Citation Graph (0, 0)][DBLP]
    Random Struct. Algorithms, 2003, v:23, n:1, pp:73-91 [Journal]
  180. Wenceslas Fernandez de la Vega, Marek Karpinski
    Polynomial time approximation of dense weighted instances of MAX-CUT. [Citation Graph (0, 0)][DBLP]
    Random Struct. Algorithms, 2000, v:16, n:4, pp:314-332 [Journal]
  181. Mikael Goldmann, Marek Karpinski
    Simulating Threshold Circuits by Majority Circuits. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1998, v:27, n:1, pp:230-246 [Journal]
  182. Dima Grigoriev, Marek Karpinski
    Computing the Additive Complexity of Algebraic Circuits with Root Extracting. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1998, v:27, n:3, pp:694-701 [Journal]
  183. Dima Grigoriev, Marek Karpinski, Michael F. Singer
    Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1990, v:19, n:6, pp:1059-1063 [Journal]
  184. Dima Grigoriev, Marek Karpinski, Michael F. Singer
    Computational Complexity of Sparse Rational Interpolation. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1994, v:23, n:1, pp:1-11 [Journal]
  185. Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel
    Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2005, v:35, n:1, pp:110-119 [Journal]
  186. Marek Karpinski, Thorsten Werther
    VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1993, v:22, n:6, pp:1276-1285 [Journal]
  187. Farid M. Ablayev, Marek Karpinski, Rustam Mubarakzjanov
    On BPP versus NPcoNP for ordered read-once branching programs. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2001, v:264, n:1, pp:127-137 [Journal]
  188. Michael Clausen, Andreas W. M. Dress, Johannes Grabmeier, Marek Karpinski
    On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1991, v:84, n:2, pp:151-164 [Journal]
  189. Elias Dahlhaus, Marek Karpinski
    Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1988, v:61, n:, pp:121-136 [Journal]
  190. Elias Dahlhaus, Marek Karpinski
    An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1994, v:134, n:2, pp:493-528 [Journal]
  191. Dima Grigoriev, Marek Karpinski
    Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1996, v:157, n:1, pp:91-99 [Journal]
  192. Marek Karpinski
    Decidability of "Skolem Matrix Emptiness Problem" Entails Constructability of Exact Regular Expression. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1982, v:17, n:, pp:99-102 [Journal]
  193. Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter
    Correctness of Constructing Optimal Alphabetic Trees Revisited. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1997, v:180, n:1-2, pp:309-324 [Journal]
  194. Marek Karpinski, Alfred J. van der Poorten, Igor Shparlinski
    Zero testing of p-adic and modular polynomials. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2000, v:233, n:1-2, pp:309-317 [Journal]
  195. Marek Karpinski, Wojciech Rytter
    Alphabet-Independent Optimal Parallel Search for Three-Dimensional Patterns. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1998, v:205, n:1-2, pp:243-260 [Journal]
  196. Marek Karpinski, Igor Shparlinski
    On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1996, v:157, n:2, pp:259-266 [Journal]
  197. Marek Karpinski, Rutger Verbeek
    On Randomized versus Deterministic Computation. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1996, v:154, n:1, pp:23-39 [Journal]
  198. Piotr Berman, Marek Karpinski, Yakov Nekrich
    Optimal trade-off for Merkle tree traversal. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2007, v:372, n:1, pp:26-36 [Journal]
  199. Sergei Evdokimov, Marek Karpinski, Ilia N. Ponomarenko
    Compact cellular algebras and permutation groups. [Citation Graph (0, 0)][DBLP]
    Discrete Mathematics, 1999, v:197, n:, pp:247-267 [Journal]

  200. Searching for Frequent Colors in Rectangles. [Citation Graph (, )][DBLP]


  201. Space Efficient Multi-dimensional Range Reporting. [Citation Graph (, )][DBLP]


  202. Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. [Citation Graph (, )][DBLP]


  203. Low-Memory Adaptive Prefix Coding. [Citation Graph (, )][DBLP]


  204. The Complexity of Perfect Matching Problems on Dense Hypergraphs. [Citation Graph (, )][DBLP]


  205. Schemes for deterministic polynomial factoring. [Citation Graph (, )][DBLP]


  206. Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. [Citation Graph (, )][DBLP]


  207. Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. [Citation Graph (, )][DBLP]


  208. Approximating Transitive Reductions for Directed Networks. [Citation Graph (, )][DBLP]


  209. 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. [Citation Graph (, )][DBLP]


  210. A Fast Algorithm for Adaptive Prefix Coding. [Citation Graph (, )][DBLP]


  211. Schemes for Deterministic Polynomial Factoring [Citation Graph (, )][DBLP]


  212. Searching for Frequent Colors in Rectangles [Citation Graph (, )][DBLP]


  213. The Mixing Time of Glauber Dynamics for Colouring Regular Trees [Citation Graph (, )][DBLP]


  214. Space-Efficient Multi-Dimensional Range Reporting [Citation Graph (, )][DBLP]


  215. Approximating Transitivity in Directed Networks [Citation Graph (, )][DBLP]


  216. 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two [Citation Graph (, )][DBLP]


  217. Trading GRH for algebra: algorithms for factoring polynomials and related structures [Citation Graph (, )][DBLP]


  218. Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems [Citation Graph (, )][DBLP]


  219. Low-Memory Adaptive Prefix Coding [Citation Graph (, )][DBLP]


  220. A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two [Citation Graph (, )][DBLP]


  221. Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications [Citation Graph (, )][DBLP]


  222. Deterministic Polynomial Time Algorithms for Matrix Completion Problems [Citation Graph (, )][DBLP]


  223. Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems [Citation Graph (, )][DBLP]


  224. Range Reporting for Moving Points on a Grid [Citation Graph (, )][DBLP]


  225. Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament [Citation Graph (, )][DBLP]


  226. Top-K Color Queries for Document Retrieval [Citation Graph (, )][DBLP]


  227. Schemes for Deterministic Polynomial Factoring. [Citation Graph (, )][DBLP]


  228. 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. [Citation Graph (, )][DBLP]


  229. Trading GRH for algebra: algorithms for factoring polynomials and related structures. [Citation Graph (, )][DBLP]


  230. Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. [Citation Graph (, )][DBLP]


  231. Approximating Transitive Reductions for Directed Networks. [Citation Graph (, )][DBLP]


  232. Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP. [Citation Graph (, )][DBLP]


  233. Approximation Complexity of Nondense Instances of MAX-CUT. [Citation Graph (, )][DBLP]


  234. On the Sample Complexity of MAX-CUT. [Citation Graph (, )][DBLP]


  235. Approximation of Global MAX-CSP Problems. [Citation Graph (, )][DBLP]


Search in 0.035secs, Finished in 0.042secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002