Complexity of Nondeterministic Graph Parameter Testing

Abstract

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.

27 pages

References in corpus (3)

• Graph limits and exchangeable random graphs
• Limits of compact decorated graphs
• Deterministic vs Non-deterministic Graph Property Testing

Cited by in corpus (2)

• On the Complexity of Nondeterministically Testable Hypergraph Parameters
• Explicit Bounds for Nondeterministically Testable Hypergraph Parameters