Marek Karpinski

Publication Activity (10 Years)

Years Active: 1973-2021
Publications (10 Years): 27

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

Algorithmica

J. Discrete Algorithms

Publications

Marek Karpinski, Igor E. Shparlinski
Noisy polynomial interpolation modulo prime powers. J. Complex. 64 (2021)
Marek Karpinski, Mateusz Lewandowski, Syed Mohammad Meesum, Matthias Mnich
Dense Steiner problems: Approximation algorithms and inapproximability. CoRR (2020)
Marek Karpinski, Igor E. Shparlinski
Noisy polynomial interpolation modulo prime powers. CoRR (2020)
Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields. Algorithmica 80 (2) (2018)
Bhaskar DasGupta, Marek Karpinski, Nasim Mobasheri, Farzane Yahyanejad
Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications. Algorithmica 80 (2) (2018)
Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Abdelhakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, N. Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
Tropical dominating sets in vertex-coloured graphs. J. Discrete Algorithms 48 (2018)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
A QPTAS for the base of the number of crossing-free structures on a planar point set. Theor. Comput. Sci. 711 (2018)
Marek Karpinski, László Mérai, Igor E. Shparlinski
Identity testing and interpolation from high powers of polynomials of large degree over finite fields. J. Complex. 49 (2018)
Marek Karpinski, Igor E. Shparlinski
Identity Testing from High Powers of Polynomials of Large Degree over Finite Fields. CoRR (2017)
Mikael Gast, Mathias Hauptmann, Marek Karpinski
Approximation Complexity of Max-Cut on Power Law Graphs. CoRR (2016)
Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, Narayanan Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
Tropical Dominating Sets in Vertex-Coloured Graphs. WALCOM (2016)
Marek Karpinski
Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies. Electron. Colloquium Comput. Complex. 22 (2015)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set. ICALP (1) (2015)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
Generalized Wong sequences and their applications to Edmonds' problems. J. Comput. Syst. Sci. 81 (7) (2015)
Marek Karpinski, Roland Markó
On the Complexity of Nondeterministically Testable Hypergraph Parameters. CoRR (2015)
Mikael Gast, Mathias Hauptmann, Marek Karpinski
Inapproximability of dominating set on power law graphs. Theor. Comput. Sci. 562 (2015)
Marek Karpinski, Richard Schmied, Claus Viehmann
Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs. J. Discrete Algorithms 33 (2015)
Marek Karpinski, Michael Lampis, Richard Schmied
New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81 (8) (2015)
Marek Karpinski
Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies. FCT (2015)
Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski
Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. CoRR (2015)
Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, N. Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
Tropical Dominating Sets in Vertex-Coloured Graphs. CoRR (2015)
Mathias Hauptmann, Marek Karpinski
On the Approximability of Independent Set Problem on Power Law Graphs. CoRR (2015)
Marek Karpinski, Roland Markó
Explicit Bounds for Nondeterministically Testable Hypergraph Parameters. CoRR (2015)
Marek Karpinski, Richard Schmied
Approximation hardness of graphic TSP on cubic graphs. RAIRO Oper. Res. 49 (4) (2015)
Bhaskar DasGupta, Marek Karpinski, Nasim Mobasheri, Farzane Yahyanejad
Node Expansions and Cuts in Gromov-hyperbolic Graphs. CoRR (2015)
Peter Bürgisser, Felipe Cucker, Marek Karpinski, Nicolai N. Vorobjov Jr.
Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242). Dagstuhl Reports 5 (6) (2015)
Mikael Gast, Mathias Hauptmann, Marek Karpinski
Approximability of TSP on Power Law Graphs. CoRR (2015)
Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
Approximate Counting of Matchings in (3, 3)-Hypergraphs. CoRR (2014)
Piotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder, Marek Karpinski
On the Computational Complexity of Measuring Global Stability of Banking Networks. Algorithmica 70 (4) (2014)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
Generalized Wong sequences and their applications to Edmonds' problems. STACS (2014)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
A QPTAS for the Base of the Number of Triangulations of a Planar Point Set. CoRR (2014)
Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
Approximate Counting of Matchings in (3, 3)-Hypergraphs. SWAT (2014)
Marek Karpinski, Roland Markó
Limits of CSP Problems and Efficient Parameter Testing. CoRR (2014)
Marek Karpinski, Roland Markó
Complexity of Nondeterministic Graph Parameter Testing. CoRR (2014)
Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
Approximate Counting of Matchings in (3,3)-Hypergraphs. Electron. Colloquium Comput. Complex. 21 (2014)
Marek Karpinski, Michael Lampis, Richard Schmied
New Inapproximability Bounds for TSP CoRR (2013)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
Generalized Wong sequences and their applications to Edmonds' problems. CoRR (2013)
Marek Karpinski, Richard Schmied
Improved Inapproximability Results for the Shortest Superstring and Related Problems. CATS (2013)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
Generalized Wong sequences and their applications to Edmonds' problems. Electron. Colloquium Comput. Complex. 20 (2013)
Marek Karpinski, Richard Schmied
Approximation Hardness of Graphic TSP on Cubic Graphs CoRR (2013)
Marek Karpinski, Richard Schmied
Approximation Hardness of Graphic TSP on Cubic Graphs. Electron. Colloquium Comput. Complex. 20 (2013)
Edyta Szymanska, Marek Karpinski, Andrzej Rucinski
Approximate Counting of Matchings in Sparse Uniform Hypergraphs. ANALCO (2013)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
Optimal cuts and partitions in tree metrics in polynomial time. Inf. Process. Lett. 113 (12) (2013)
Marek Karpinski, Michael Lampis, Richard Schmied
New Inapproximability Bounds for TSP. ISAAC (2013)
Satabdi Aditya, Bhaskar DasGupta, Marek Karpinski
Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks. CoRR (2013)
Marek Karpinski, Michael Lampis, Richard Schmied
New Inapproximability Bounds for TSP. Electron. Colloquium Comput. Complex. 20 (2013)
Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
Approximate Counting of Matchings in Sparse Hypergraphs CoRR (2012)
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic Polynomial Factoring and Association Schemes CoRR (2012)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time CoRR (2012)
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena
Trading GRH for algebra: Algorithms for factoring polynomials and related structures. Math. Comput. 81 (277) (2012)
Mikael Gast, Mathias Hauptmann, Marek Karpinski
Inapproximability of Dominating Set in Power Law Graphs CoRR (2012)
Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
Approximate Counting of Matchings in Sparse Uniform Hypergraphs CoRR (2012)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
Optimal Cuts and Bisections on the Real Line in Polynomial Time CoRR (2012)
Marek Karpinski, Richard Schmied
On Approximation Lower Bounds for TSP with Bounded Metrics. Electron. Colloquium Comput. Complex. 19 (2012)
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic Polynomial Factoring and Association Schemes. Electron. Colloquium Comput. Complex. 19 (2012)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time. Electron. Colloquium Comput. Complex. 19 (2012)
Marek Karpinski, Richard Schmied
On Approximation Lower Bounds for TSP with Bounded Metrics CoRR (2012)
Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann
Approximating vertex cover in dense hypergraphs. J. Discrete Algorithms 13 (2012)
Piotr Berman, Marek Karpinski, Andrzej Lingas
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. Algorithmica 64 (2) (2012)
Mikael Gast, Mathias Hauptmann, Marek Karpinski
Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations CoRR (2012)
Marek Karpinski, Richard Schmied, Claus Viehmann
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs. Electron. Colloquium Comput. Complex. 18 (2011)
Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports 1 (6) (2011)
Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann
Approximating Subdense Instances of Covering Problems. Electron. Notes Discret. Math. 37 (2011)
Marek Karpinski, Warren Schudy
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. APPROX-RANDOM (2011)
Marek Karpinski, Richard Schmied
Improved Lower Bounds for the Shortest Superstring and Related Problems. Electron. Colloquium Comput. Complex. 18 (2011)
Marek Karpinski, Yakov Nekrich
Top-K Color Queries for Document Retrieval. SODA (2011)
Marek Karpinski, Richard Schmied
Improved Lower Bounds for the Shortest Superstring and Related Problems CoRR (2011)
Piotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder, Marek Karpinski
On Systemic Stability of Banking Networks CoRR (2011)
Marek Karpinski, Richard Schmied, Claus Viehmann
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs CoRR (2011)
Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. LATIN (2010)
Piotr Berman, Marek Karpinski, Alexander Zelikovsky
A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. ISAAC (1) (2010)
Marek Karpinski, Yakov Nekrich
Top-K Color Queries for Document Retrieval CoRR (2010)
Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann
Approximating Subdense Instances of Covering Problems CoRR (2010)
Abdelfattah Abouelaoualim, Kinkar Chandra Das, Wenceslas Fernandez de la Vega, Marek Karpinski, Yannis Manoussakis, Carlos A. J. Martinhon, Rachid Saad
Cycles and paths in edge-colored graphs with given degrees. J. Graph Theory 64 (1) (2010)
Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann
Approximating Vertex Cover in Dense Hypergraphs CoRR (2010)
Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density. Int. J. Found. Comput. Sci. 21 (6) (2010)
Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
The mixing time of Glauber dynamics for coloring regular trees. Random Struct. Algorithms 36 (4) (2010)
Piotr Berman, Marek Karpinski, Andrzej Lingas
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. COCOON (2010)
Marek Karpinski, Warren Schudy
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament CoRR (2010)
Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic Polynomial Time Algorithms for Matrix Completion Problems. SIAM J. Comput. 39 (8) (2010)
Marek Karpinski, Warren Schudy
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. ISAAC (1) (2010)
Marek Karpinski, J. Ian Munro, Yakov Nekrich
Range Reporting for Moving Points on a Grid CoRR (2010)
Travis Gagie, Marek Karpinski, Yakov Nekrich
Low-Memory Adaptive Prefix Coding. DCC (2009)
Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic Polynomial Time Algorithms for Matrix Completion Problems CoRR (2009)
Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
The Complexity of Perfect Matching Problems on Dense Hypergraphs. ISAAC (2009)
Piotr Berman, Marek Karpinski, Andrzej Lingas
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications CoRR (2009)
Marek Karpinski, Yakov Nekrich
Space Efficient Multi-dimensional Range Reporting. COCOON (2009)
Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic Polynomial Time Algorithms for Matrix Completion Problems. Electron. Colloquium Comput. Complex. 16 (2009)
Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Schemes for deterministic polynomial factoring. ISSAC (2009)
Piotr Berman, Marek Karpinski, Alexander Zelikovsky
1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. WADS (2009)
Piotr Berman, Bhaskar DasGupta, Marek Karpinski
Approximating Transitive Reductions for Directed Networks. WADS (2009)
Marek Karpinski, Warren Schudy
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems CoRR (2009)
Marek Karpinski, Yakov Nekrich
A Fast Algorithm for Adaptive Prefix Coding. Algorithmica 55 (1) (2009)
Marek Karpinski, Warren Schudy
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. STOC (2009)
Piotr Berman, Marek Karpinski, Alexander Zelikovsky
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two CoRR (2008)
Marek Karpinski, Yakov Nekrich
Searching for Frequent Colors in Rectangles. CCCG (2008)
Piotr Berman, Marek Karpinski, Alexander Zelikovsky
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. Electron. Colloquium Comput. Complex. 15 (094) (2008)
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena
Trading GRH for algebra: algorithms for factoring polynomials and related structures. Electron. Colloquium Comput. Complex. 15 (099) (2008)
Travis Gagie, Marek Karpinski, Yakov Nekrich
Low-Memory Adaptive Prefix Coding CoRR (2008)
Marek Karpinski, Warren Schudy
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems CoRR (2008)

Marek Karpinski.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Marek Karpinski