Marek Karpinski
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Marek Karpinski has a total of 65 co-authors. Here are the top co-authors by number of shared publications:
- Gábor Ivanyos
HUN-REN Institute for Computer Science and Control Budapest Hungary
10 shared publications - Andrzej Lingas
Department of Computer Science Lund University Lund Sweden
8 shared publications - Nitin Saxena
IIT Kanpur, Kanpur, India
8 shared publications - Richard Schmied
Dept. of Computer Science University of Bonn. Work supported by Hausdorff Doctoral Fellowship
8 shared publications - Piotr Berman
Pennsylvania State University
7 shared publications - Bhaskar DasGupta
University of Illinois
6 shared publications
Latest Publications
- Open Access
Noisy polynomial interpolation modulo prime powers
We consider the {\it noisy polynomial interpolation problem\/} of recovering an unknown $s$-sparse polynomial $f(X)$ over the ring $\mathbb Z_{p^k}$ of residues modulo $p^k$, where $p$ is a small prime and $k$ is a large integer parameter, from approximate values of the residues of $f(t) \in \mathbb Z_{p^k}$. Similar results are known for residues modulo a large prime $p$, however the case of prime power modulus $p^k$, with small $p$ and large $k$, is new and requires different techniques. We give a deterministic polynomial time algorithm, which for almost given more than a half bits of $f(t)$ for sufficiently many randomly chosen points $t \in \mathbb Z_{p^k}^*$, recovers $f(X)$.Open AccessNoisy polynomial interpolation modulo prime powers
We consider the {\it noisy polynomial interpolation problem\/} of recovering an unknown $s$-sparse polynomial $f(X)$ over the ring $\mathbb Z_{p^k}$ of residues modulo $p^k$, where $p$ is a small prime and $k$ is a large integer parameter, from approximate values of the residues of $f(t) \in \mathbb Z_{p^k}$. Similar results are known for residues modulo a large prime $p$, however the case of prime power modulus $p^k$, with small $p$ and large $k$, is new and requires different techniques. We give a deterministic polynomial time algorithm, which for almost given more than a half bits of $f(t)$ for sufficiently many randomly chosen points $t \in \mathbb Z_{p^k}^*$, recovers $f(X)$. - 1 December 2018
- Published by Elsevier in Journal of Complexity
- Vol. 49, 74-84
Identity testing and interpolation from high powers of polynomials of large degree over finite fields
- 1 December 2018
- Published by Elsevier in Journal of Complexity
- Vol. 49, 74-84
Identity testing and interpolation from high powers of polynomials of large degree over finite fields
- Open Access
Identity Testing and Interpolation from High Powers of Polynomials of Large Degree over Finite Fields
We consider the problem of identity testing and recovering (that is, interpolating) of a "hidden" monic polynomials $f$, given an oracle access to $f(x)^e$ for $x\in\mathbb F_q$, where $\mathbb F_q$ is the finite field of $q$ elements and an extension fields access is not permitted. The naive interpolation algorithm needs $de+1$ queries, where $d =\max\{{\rm deg}\ f, {\rm deg }\ g\}$ and thus requires $ de<q$. For a prime $q = p$, we design an algorithm that is asymptotically better in certain cases, especially when $d$ is large. The algorithm is based on a result of independent interest in spirit of additive combinatorics. It gives an upper bound on the number of values of a rational function of large degree, evaluated on a short sequence of consecutive integers, that belong to a small subgroup of $\mathbb F_p^*$.Open AccessIdentity Testing and Interpolation from High Powers of Polynomials of Large Degree over Finite Fields
We consider the problem of identity testing and recovering (that is, interpolating) of a "hidden" monic polynomials $f$, given an oracle access to $f(x)^e$ for $x\in\mathbb F_q$, where $\mathbb F_q$ is the finite field of $q$ elements and an extension fields access is not permitted. The naive interpolation algorithm needs $de+1$ queries, where $d =\max\{{\rm deg}\ f, {\rm deg }\ g\}$ and thus requires $ de<q$. For a prime $q = p$, we design an algorithm that is asymptotically better in certain cases, especially when $d$ is large. The algorithm is based on a result of independent interest in spirit of additive combinatorics. It gives an upper bound on the number of values of a rational function of large degree, evaluated on a short sequence of consecutive integers, that belong to a small subgroup of $\mathbb F_p^*$. - 1 February 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 711, 56-65
A QPTAS for the base of the number of crossing-free structures on a planar point set
- 1 February 2018
- Published by Elsevier in Theoretical Computer Science
- Vol. 711, 56-65
A QPTAS for the base of the number of crossing-free structures on a planar point set
- Open Access
Approximate Counting of Matchings in $(3,3)$-Hypergraphs
We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting problem for 3-partite $(3,3)$-hypergraphs. The proof technique of this paper uses the general correlation decay technique and a new combinatorial analysis of the underlying structures of the intersection graphs. The proof method could be also of independent interest.
Open AccessApproximate Counting of Matchings in $(3,3)$-Hypergraphs
We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting problem for 3-partite $(3,3)$-hypergraphs. The proof technique of this paper uses the general correlation decay technique and a new combinatorial analysis of the underlying structures of the intersection graphs. The proof method could be also of independent interest.
- 17 February 2017
- Published by Springer Nature in Algorithmica
- Vol. 80 (2) , 772-800
Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
- 17 February 2017
- Published by Springer Nature in Algorithmica
- Vol. 80 (2) , 772-800
Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
- Open Access
Effect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
$\delta$-hyperbolic graphs, originally conceived by Gromov in 1987, occur often in many network applications; for fixed $\delta$, such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of "non-expander" graphs. The main motivation of this paper is to investigate the effect of the hyperbolicity measure $\delta$ on expansion and cut-size bounds on graphs (here $\delta$ need not be a constant), and the asymptotic ranges of $\delta$ for which these results may provide improved approximation algorithms for related combinatorial problems. To this effect, we provide constructive bounds on node expansions for $\delta$-hyperbolic graphs as a function of $\delta$, and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently even if the witnesses are required to be nested or sufficiently distinct from each other. To the best of our knowledge, these are the first such constructive bounds proven. We also show how to find a large family of s-t cuts with relatively small number of cut-edges when s and t are sufficiently far apart. We then provide algorithmic consequences of these bounds and their related proof techniques for two problems for $\delta$-hyperbolic graphs (where $\delta$ is a function $f$ of the number of nodes, the exact nature of growth of $f$ being dependent on the particular problem considered).Open AccessEffect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
$\delta$-hyperbolic graphs, originally conceived by Gromov in 1987, occur often in many network applications; for fixed $\delta$, such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of "non-expander" graphs. The main motivation of this paper is to investigate the effect of the hyperbolicity measure $\delta$ on expansion and cut-size bounds on graphs (here $\delta$ need not be a constant), and the asymptotic ranges of $\delta$ for which these results may provide improved approximation algorithms for related combinatorial problems. To this effect, we provide constructive bounds on node expansions for $\delta$-hyperbolic graphs as a function of $\delta$, and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently even if the witnesses are required to be nested or sufficiently distinct from each other. To the best of our knowledge, these are the first such constructive bounds proven. We also show how to find a large family of s-t cuts with relatively small number of cut-edges when s and t are sufficiently far apart. We then provide algorithmic consequences of these bounds and their related proof techniques for two problems for $\delta$-hyperbolic graphs (where $\delta$ is a function $f$ of the number of nodes, the exact nature of growth of $f$ being dependent on the particular problem considered). - 5 January 2017
- Published by Springer Nature in Algorithmica
- Vol. 80 (2) , 560-575
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields
- 5 January 2017
- Published by Springer Nature in Algorithmica
- Vol. 80 (2) , 560-575
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields
- Open Access
Limits of CSP Problems and Efficient Parameter Testing
We present a unified framework on the limits of constraint satisfaction problems (CSPs) and efficient parameter testing which depends only on array exchangeability and the method of cut decomposition without recourse to the weakly regular partitions. In particular, we formulate and prove a representation theorem for compact colored $r$-uniform directed hypergraph ($r$-graph) limits, and apply this to $r$CSP limits. We investigate the sample complexity of testable $r$-graph parameters, we discuss the generalized ground state energies and demonstrate that they are efficiently testable.
Open AccessLimits of CSP Problems and Efficient Parameter Testing
We present a unified framework on the limits of constraint satisfaction problems (CSPs) and efficient parameter testing which depends only on array exchangeability and the method of cut decomposition without recourse to the weakly regular partitions. In particular, we formulate and prove a representation theorem for compact colored $r$-uniform directed hypergraph ($r$-graph) limits, and apply this to $r$CSP limits. We investigate the sample complexity of testable $r$-graph parameters, we discuss the generalized ground state energies and demonstrate that they are efficiently testable.
- Open Access
Approximation Complexity of Max-Cut on Power Law Graphs
In this paper we study the MAX-CUT problem on power law graphs (PLGs) with power law exponent $\beta$. We prove some new approximability results on that problem. In particular we show that there exist polynomial time approximation schemes (PTAS) for MAX-CUT on PLGs for the power law exponent $\beta$ in the interval $(0,2)$. For $\beta>2$ we show that for some $\epsilon>0$, MAX-CUT is NP-hard to approximate within approximation ratio $1+\epsilon$, ruling out the existence of a PTAS in this case. Moreover we give an approximation algorithm with improved constant approximation ratio for the case of $\beta>2$.Open AccessApproximation Complexity of Max-Cut on Power Law Graphs
In this paper we study the MAX-CUT problem on power law graphs (PLGs) with power law exponent $\beta$. We prove some new approximability results on that problem. In particular we show that there exist polynomial time approximation schemes (PTAS) for MAX-CUT on PLGs for the power law exponent $\beta$ in the interval $(0,2)$. For $\beta>2$ we show that for some $\epsilon>0$, MAX-CUT is NP-hard to approximate within approximation ratio $1+\epsilon$, ruling out the existence of a PTAS in this case. Moreover we give an approximation algorithm with improved constant approximation ratio for the case of $\beta>2$.