22 citations · 138 across the 41 of their papers we have counts for
52 papers
Noisy polynomial interpolation modulo prime powers
Marek Karpinski, Igor Shparlinski
We consider the {\it noisy polynomial interpolation problem\/} of recovering an unknown -sparse polynomial over the ring of residues modulo , where…
Dense Steiner problems: Approximation algorithms and inapproximability
Marek Karpinski, Mateusz Lewandowski, Syed Mohammad Meesum +1
The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set of terminals in a graph by a tree of minimum size. Karpinski and…
Identity Testing and Interpolation from High Powers of Polynomials of Large Degree over Finite Fields
Marek Karpinski, Laszlo Mérai, Igor E. Shparlinski
We consider the problem of identity testing and recovering (that is, interpolating) of a "hidden" monic polynomials , given an oracle access to for , w…
Approximation Complexity of Max-Cut on Power Law Graphs
Mikael Gast, Mathias Hauptmann, Marek Karpinski
In this paper we study the MAX-CUT problem on power law graphs (PLGs) with power law exponent . We prove some new approximability results on that problem. In particular we show…
Effect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
Bhaskar DasGupta, Marek Karpinski, Nasim Mobasheri +1
-hyperbolic graphs, originally conceived by Gromov in 1987, occur often in many network applications; for fixed , such graphs are simply called hyperbolic graphs and include…
Approximability of TSP on Power Law Graphs
Mikael Gast, Mathias Hauptmann, Marek Karpinski
In this paper we study the special case of Graphic TSP where the underlying graph is a power law graph (PLG). We give a refined analysis of some of the current best approximation a…