| 2016 | WALCOM | Tropical Dominating Sets in Vertex-Coloured Graphs. | Jean-Alexandre Angls d'Auriac, Csilla Bujts, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, Narayanan Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza |
| 2015 | FCT | Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies. | Marek Karpinski |
| 2015 | ICALP | A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set. | Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu |
| 2014 | STACS | Generalized Wong sequences and their applications to Edmonds' problems. | Gbor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha |
| 2013 | ISAAC | New Inapproximability Bounds for TSP. | Marek Karpinski, Michael Lampis, Richard Schmied |
| 2011 | SODA | Top-K Color Queries for Document Retrieval. | Marek Karpinski, Yakov Nekrich |
| 2010 | COCOON | Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. | Piotr Berman, Marek Karpinski, Andrzej Lingas |
| 2010 | ISAAC | A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. | Piotr Berman, Marek Karpinski, Alexander Zelikovsky |
| 2010 | ISAAC | Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. | Marek Karpinski, Warren Schudy |
| 2010 | LATIN | Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
| 2009 | COCOON | Space Efficient Multi-dimensional Range Reporting. | Marek Karpinski, Yakov Nekrich |
| 2009 | DCC | Low-Memory Adaptive Prefix Coding. | Travis Gagie, Marek Karpinski, Yakov Nekrich |
| 2009 | ISAAC | The Complexity of Perfect Matching Problems on Dense Hypergraphs. | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
| 2009 | ISSAC | Schemes for deterministic polynomial factoring. | Gbor Ivanyos, Marek Karpinski, Nitin Saxena |
| 2009 | STOC | Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. | Marek Karpinski, Warren Schudy |
| 2009 | WADS | Approximating Transitive Reductions for Directed Networks. | Piotr Berman, Bhaskar DasGupta, Marek Karpinski |
| 2009 | WADS | 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. | Piotr Berman, Marek Karpinski, Alexander Zelikovsky |
| 2006 | ICALP | Stopping Times, Metrics and Approximate Counting. | Magnus Bordewich, Martin E. Dyer, Marek Karpinski |
| 2006 | ISIT | A Fast Algorithm for Adaptive Prefix Coding. | Marek Karpinski, Yakov Nekrich |
| 2006 | SODA | 8/7-approximation algorithm for (1, 2)-TSP. | Piotr Berman, Marek Karpinski |
| 2005 | DCC | Algorithms for Construction of Optimal and Almost-Optimal Length-Restricted Codes. | Marek Karpinski, Yakov Nekrich |
| 2005 | ESA | Predecessor Queries in Constant Time?. | Marek Karpinski, Yakov Nekrich |
| 2005 | FCT | Path Coupling Using Stopping Times. | Magnus Bordewich, Martin E. Dyer, Marek Karpinski |
| 2005 | ISAAC | On the Complexity of Global Constraint Satisfaction. | Cristina Bazgan, Marek Karpinski |
| 2005 | ISAAC | Embedding Point Sets into Plane Graphs of Small Dilation. | Annette Ebbers-Baumann, Ansgar Grne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas |
| 2005 | STOC | Tensor decomposition and approximation schemes for constraint satisfaction problems. | Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala |
| 2004 | SODA | Approximation schemes for Metric Bisection and partitioning. | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon |
| 2003 | STOC | Approximation schemes for clustering problems. | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani |
| 2003 | WADS | Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem. | Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky |
| 2002 | ESA | 1.375-Approximation Algorithm for Sorting by Reversals. | Piotr Berman, Sridhar Hannenhalli, Marek Karpinski |
| 2002 | ICALP | Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. | Piotr Berman, Marek Karpinski |
| 2002 | ICALP | Approximating Huffman Codes in Parallel. | Piotr Berman, Marek Karpinski, Yakov Nekrich |
| 2002 | MFCS | Approximability of the Minimum Bisection Problem: An Algorithmic Challenge. | Marek Karpinski |
| 2002 | SODA | Approximating minimum unsatisfiability of linear equations. | Piotr Berman, Marek Karpinski |
| 2002 | SODA | Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. | Bla Csaba, Marek Karpinski, Piotr Krysta |
| 2002 | STOC | Random sampling and approximation of MAX-CSP problems. | Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski |
| 2001 | FCT | On Computational Power of Quantum Branching Programs. | Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski |
| 2001 | FCT | Approximating Bounded Degree Instances of NP-Hard Problems. | Marek Karpinski |
| 2001 | ICALP | Approximation Hardness of TSP with Bounded Metrics. | Lars Engebretsen, Marek Karpinski |
| 2001 | STACS | Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. | Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel |
| 1999 | FCT | Randomized Complexity of Linear Arrangements and Polyhedra. | Marek Karpinski |
| 1999 | ICALP | On Some Tighter Inapproximability Results (Extended Abstract). | Piotr Berman, Marek Karpinski |
| 1999 | SOFSEM | Quantum Finite Multitape Automata. | Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski |
| 1998 | STOC | An Exponential Lower Bound for Depth 3 Arithmetic Circuits. | Dima Grigoriev, Marek Karpinski |
| 1997 | ALT | Effects of Kolmogorov Complexity Present in Inductive Inference as Well. | Andris Ambainis, Kalvis Apsitis, Cristian Calude, Rusins Freivalds, Marek Karpinski, Tomas Larfeldt, Iveta Sala, Juris Smotrovs |
| 1997 | CPM | On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. | Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter |
| 1997 | ISSAC | Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. | Alexander L. Chistov, Gbor Ivanyos, Marek Karpinski |
| 1997 | STOC | Randomized Omega(n | Dima Grigoriev, Marek Karpinski |
| 1997 | WADS | On-line Load Balancing for Related Machines. | Piotr Berman, Moses Charikar, Marek Karpinski |
| 1996 | CPM | Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract). | Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter |
| 1996 | ICALP | On the Power of Randomized Branching Programs. | Farid M. Ablayev, Marek Karpinski |
| 1996 | SODA | Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees. | Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter |
| 1996 | STOC | A Lower Bound for Randomized Algebraic Decision Trees. | Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky |
| 1995 | CPM | Pattern-Matching for Strings with Short Descriptions. | Marek Karpinski, Wojciech Rytter, Ayumi Shinohara |
| 1995 | FOCS | Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. | Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr. |
| 1995 | ICALP | Lower Time Bounds for Randomized Computation. | Rusins Freivalds, Marek Karpinski |
| 1995 | STOC | Polynomial time approximation schemes for dense instances of | Sanjeev Arora, David R. Karger, Marek Karpinski |
| 1995 | STOC | On real Turing machines that toss coins. | Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther |
| 1995 | STOC | Polynomial bounds for VC dimension of sigmoidal neural networks. | Marek Karpinski, Angus Macintyre |
| 1994 | ALT | Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions. | Rusins Freivalds, Dace Gobleja, Marek Karpinski, Carl H. Smith |
| 1994 | COLT | Co-Learning of Total Recursive Functions. | Rusins Freivalds, Marek Karpinski, Carl H. Smith |
| 1994 | CPM | An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern. | Marek Karpinski, Wojciech Rytter |
| 1994 | ESA | Approaching the 5/4-Approximation for Rectilinear Steiner Trees. | Piotr Berman, Ulrich Fmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky |
| 1994 | ICALP | Lower Space Bounds for Randomized Computation. | Rusins Freivalds, Marek Karpinski |
| 1994 | MFCS | On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. | Marek Karpinski, Wojciech Rytter |
| 1994 | STOC | Lower bounds on testing membership to a polyhedron by algebraic decision trees. | Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr. |
| 1993 | ICALP | On Randomized Versus Deterministic Computation. | Marek Karpinski, Rutger Verbeek |
| 1993 | STOC | Counting curves and their projections. | Joachim von zur Gathen, Marek Karpinski, Igor E. Shparlinski |
| 1993 | STOC | Simulating threshold circuits by majority circuits. | Mikael Goldmann, Marek Karpinski |
| 1992 | ISSAC | Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. | Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko |
| 1991 | FCT | Approximation Algorithms for Counting Problems in Finite Fields. | Marek Karpinski |
| 1991 | FOCS | An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] | Dima Grigoriev, Marek Karpinski |
| 1991 | ISSAC | Algorithms for Sparse Rational Interpolation. | Dima Grigoriev, Marek Karpinski |
| 1991 | SODA | Approximating the Number of Zeroes of a GF[2] Polynomial. | Marek Karpinski, Michael Luby |
| 1990 | CSL | Subclasses of Quantified Boolean Formulas. | Andreas Flgel, Marek Karpinski, Hans Kleine Bning |
| 1990 | FOCS | Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents | Dima Grigoriev, Marek Karpinski, Michael F. Singer |
| 1990 | MFCS | On the Complexity of Genuinely Polynomial Computation. | Marek Karpinski, Friedhelm Meyer auf der Heide |
| 1990 | SODA | Fast Parallel Algorithms for the Clique Separator Decomposition. | Elias Dahlhaus, Marek Karpinski, Mark B. Novick |
| 1989 | COLT | Learning Read-Once Formulas Using Membership Queries. | Lisa Hellerstein, Marek Karpinski |
| 1989 | FOCS | An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract) | Elias Dahlhaus, Marek Karpinski |
| 1988 | CSL | Boolean Complexity of Algebraic Interpolation Problems. | Marek Karpinski |
| 1988 | FOCS | Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs | Elias Dahlhaus, Pter Hajnal, Marek Karpinski |
| 1988 | ISMIS | Learning Machine for Probabilistically Describable Concepts. | Marek Karpinski, Zbigniew W. Ras |
| 1987 | CSL | On the Computational Complexity of Quantified Horn Clauses. | Marek Karpinski, Hans Kleine Bning, Peter H. Schmitt |
| 1987 | FOCS | The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) | Dima Grigoriev, Marek Karpinski |
| 1979 | FCT | Decidability Results on Plane Automata Searching Mazes. | Ryszard Danecki, Marek Karpinski |
| 1977 | FCT | The Equivalences Problems for Binary EOL-Systems are Decidable. | Marek Karpinski |
| 1976 | MFCS | Multiplicity Functions on Omega-Automata. | Marek Karpinski |
| 1975 | MFCS | Decision Algorithms for Havel's Branching Automata. | Marek Karpinski |
| 1974 | MFCS | Stretching by Probabilistic Tree Automata and Santos Grammars. | Marek Karpinski |