Testing versus Estimation of Graph Properties

DOI10.1137/060652324MaRDI QIDQ5386210zbMATH OpenOpenAlexWikidataFDO

Authors Eldar Fischer, Ilan Newman

Publication date 22 April 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/060652324

zbMATH Keywords

approximationgraph algorithmsproperty testingregularity Lemma

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• scientific article; zbMATH DE number 1241385
• Property testing and its connection to learning and approximation
• Tolerant property testing and distance approximation
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Algorithmic Aspects of Property Testing in the Dense Graphs Model

Cited in

(22)

• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• Graph limits and parameter testing
• Tolerant versus intolerant testing for Boolean properties
• Contemplations on Testing Graph Properties
• Estimating parameters associated with monotone properties
• Testing Eulerianity and connectivity in directed sparse graphs
• Sample-based distance-approximation for subsequence-freeness
• Earthmover Resilience and Testing in Ordered Structures
• Estimating parameters associated with monotone properties
• On the benefits of adaptivity in property testing of dense graphs
• Ordered graph limits and their applications
• Testing versus estimation of graph properties, revisited
• On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
• Parameter testing in bounded degree graphs of subexponential growth
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Inflatable graph properties and natural property tests
• Local-vs-global combinatorics
• Approximating the distance to monotonicity of Boolean functions
• Deterministic vs non-deterministic graph property testing
• Estimating the distance to a hereditary graph property
• Brief announcement: Erasure-resilience versus tolerance to errors
• A characterization of testable hypergraph properties

This page was built for publication: Testing versus Estimation of Graph Properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5386210)