9 citations · 16 across the 6 of their papers we have counts for
6 papers
Explicit Bounds for Nondeterministically Testable Hypergraph Parameters
Marek Karpinski, Roland Markó
In this note we give a new effective proof method for the equivalence of the notions of testability and nondeterministic testability for uniform hypergraph parameters. We provide t…
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…
Complexity of Nondeterministic Graph Parameter Testing
Marek Karpinski, Roland Markó
We study the sample complexity of nondeterministically testable graph parameters and improve existing bounds on it by several orders of magnitude. The technique used would be also…
Lower threshold ground state energy and testability of minimal balanced cut density
András Krámli, Roland Markó
Lovász and his coauthors defined the notion of microcanonical ground state energy -- borrowed from the statistical physics -- for weighted grap…
Limits of CSP Problems and Efficient Parameter Testing
Marek Karpinski, Roland Markó
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 o…
A Poisson allocation of optimal tail
Roland Markó, Ádám Timár
The allocation problem for a -dimensional Poisson point process is to find a way to partition the space to parts of equal size, and to assign the parts to the configuration poin…