Non-Deterministic Graph Property Testing
LÁSZLÓ LOVÁSZ, KATALIN VESZTERGOMBI
Source record
Source: Crossref
Published: Jul 3, 2013
DOI: 10.1017/s0963548313000205
Open original source ↗Source abstract
A property of finite graphs is called non-deterministically testable if it has a ‘certificate’ such that once the certificate is specified, its correctness can be verified by random local testing. In this paper we study certificates that consist of one or more unary and/or binary relations on the nodes, in the case of dense graphs. Using the theory of graph limits, we prove that non-deterministically testable properties are also deterministically testable.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.