Recognition: unknown
Complexity of Nondeterministic Graph Parameter Testing
classification
💻 cs.DS
math.CO
keywords
complexitygraphnondeterministictestingarbitraryboundscasediscuss
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.