16 citations · 41 across the 20 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015★ 2 cited
On the Complexity of Nondeterministically Testable Hypergraph Parameters
Marek Karpinski, Roland Markó
The paper proves the equivalence of the notions of nondeterministic and deterministic parameter testing for uniform dense hypergraphs of arbitrary order. It generalizes the result…
cs.DS2015
On the Approximability of Independent Set Problem on Power Law Graphs
Mathias Hauptmann, Marek Karpinski
We give the first nonconstant lower bounds for the approximability of the Independent Set Problem on the Power Law Graphs. These bounds are of the form in the case when the p…
math.NT2015★ 4 cited
Polynomial Interpolation and Identity Testing from High Powers over Finite Fields
Gabor Ivanyos, Marek Karpinski, Miklos Santha +2
We consider the problem of recovering (that is, interpolating) and identity testing of a "hidden" monic polynomial , given an oracle access to for (…