9 citations · 16 across the 6 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.DS2014★ 2 cited
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…
math.PR2014
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…
cs.DS2014★ 2 cited
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…