Non-Deterministic Graph Property Testing

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.

• Publication year

  2012

• Venue

  Combinatorics, probability & computing

• Publication date

  2012-02-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1017/S0963548313000205arXiv 1202.5337
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Convergent Sequences of Dense Graphs II. Multiway Cuts and Statistical Physics

  2012cited by this paper
• Property testing: current research and surveys

  2010cited by this paper
• Limits of compact decorated graphs

  2010cited by this paper
• Testing properties of graphs and functions

  2008cited by this paper
• Limits of Hypergraphs, Removal and Regularity Lemmas. A Non-standard Approach

  2007cited by this paper
• Szemerédi’s Lemma for the Analyst

  2007cited by this paper
• Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing

  2007cited by this paper
• Topics in Discrete Mathematics

  2006cited by this paper
• A combinatorial characterization of the testable graph properties: it's all about regularity

  2006cited by this paper
• Counting Graph Homomorphisms

  2006cited by this paper
• A characterization of the (natural) graph properties testable with one-sided error

  2005cited by this paper
• Testing versus estimation of graph properties

  2005cited by this paper
• Limits of dense graph sequences

  2004cited by this paper
• THE ART OF UNINFORMED DECISIONS: A PRIMER TO PROPERTY TESTING

  2004cited by this paper
• A Review of Graph Grammars and Preview of ICGT 2002: The First International Conference on Graph Transformation.

  2001cited by this paper
• Efficient Testing of Large Graphs

  2000cited by this paper
• Quick Approximation to Matrices and Applications

  1999cited by this paper
• Property testing and its connection to learning and approximation

  1996influential reference
• Robust Characterizations of Polynomials with Applications to Program Testing

  1996cited by this paper
• Polynomial time approximation schemes for dense instances of NP-hard problems

  1995cited by this paper
• Theory of the integral

  1939cited by this paper
• Large Networks and Graph Limits

  year unknowncited by this paper

• Continuous Social Networks

  2024cites this paper
• Dense networks of integrate-and-fire neurons: Spatially-extended mean-field limit of the empirical measure

  2024cites this paper
• Mean Field Games on Weighted and Directed Graphs via Colored Digraphons

  2022cites this paper
• Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms

  2022cites this paper
• Efficient Evolutionary Models with Digraphons

  2021cites this paper
• A Statistical Test of Heterogeneous Subgraph Densities to Assess Clusterability

  2019cites this paper
• Property Testing: Monotonicity and regular languages, Lower bounds

  2019cites this paper
• Probability and Computing

  2018cites this paper
• Local verification of global proofs

  2018cites this paper
• Testing Graph Clusterability: Algorithms and Lower Bounds

  2018cites this paper
• Local certification in distributed computing: error-sensitivity, uniformity, redundancy, and interactivity. (Certification locale en calcul distribué : sensibilité aux erreurs, uniformité, redondance et interactivité)

  2018cites this paper
• Error-Sensitive Proof-Labeling Schemes

  2017cites this paper
• A Characterization of Testable Hypergraph Properties

  2017cites this paper
• Minimizing Quadratic Functions in Constant Time

  2016cites this paper
• On the Complexity of Nondeterministically Testable Hypergraph Parameters

  2015cites this paper
• Explicit Bounds for Nondeterministically Testable Hypergraph Parameters

  2015influential citation
• Non-interactive proofs of proximity

  2015cites this paper
• Approximate Membership for Words and Trees

  2014cites this paper
• Complexity of Nondeterministic Graph Parameter Testing

  2014influential citation
• Deterministic vs non-deterministic graph property testing

  2013influential citation
• Limits of locally–globally convergent graph sequences

  2012cites this paper