Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2015 Copyright 2015 Universität Bonn, Institut für Informatik, Abt. V


Explicit Bounds for Nondeterministically Testable Hypergraph Parameters
Marek Karpinski and Roland Marko
[Download PostScript] [Download PDF]

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 the first effective upper bound on the sample complexity of any nondeter- ministically testable r-uniform hypergraph parameter as a function of the sample complexity of its witness parameter for arbitrary r. The dependence is of the form of an exponential tower function with the height linear in r. Our argument depends crucially on the new upper bounds for the r-cut norm of sampled r-uniform hyper- graphs. We employ also our approach for some other restricted classes of hypergraph parameters, and present some applications.

Last Change: 09/11/15 at 07:40:08
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope