Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2016 Copyright 2016 University of Bonn, Department of Computer Science, Abt. V
89167

13.07.2016

Complexity of Nondeterministic Graph Parameter Testing
(Revised Version)
Marek Karpinski, Roland Marko
[Download PostScript] [Download PDF]

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 of independent interest. We also discuss the special case of weak nondeterministic testing for uniform hypergraphs of arbitrary order.

Last Change: 07/14/16 at 11:36:59
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V