  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.
