Introduction to testing graph properties

DOI10.1007/978-3-642-22670-0_32MaRDI QIDQ3088198zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 19 August 2011

Published in Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22670-0_32

zbMATH Keywords

randomized algorithmsgraph propertiesapproximation problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Introduction to testing graph properties
• A brief introduction to property testing
• scientific article; zbMATH DE number 1857651
• Property testing and its connection to learning and approximation
• The subgraph testing model

Cites work

• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• scientific article; zbMATH DE number 5764842 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1306876 (Why is no real title available?)
• scientific article; zbMATH DE number 1756011 (Why is no real title available?)
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• A brief introduction to property testing
• A combinatorial characterization of the testable graph properties, it's all about regularity
• A separation theorem in property testing
• A sublinear bipartiteness tester for bounded degree graphs
• Algorithmic and analysis techniques in property testing
• An Expansion Tester for Bounded Degree Graphs
• Approximate hypergraph partitioning and applications
• Approximating average parameters of graphs
• Approximation algorithms for NP-hard problems.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Computational Complexity
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• Efficient testing of large graphs
• Every monotone graph property is testable
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Hierarchy theorems for property testing
• Local Graph Partitions for Approximation and Testing
• Lower bounds for sampling algorithms for estimating the average
• MAX-CUT has a randomized approximation scheme in dense graphs
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Testing \(k\)-colorability
• Testing graph isomorphism
• Testing properties of directed graphs: acyclicity and connectivity*
• Testing subgraphs in directed graphs
• Testing subgraphs in large graphs
• Testing the diameter of graphs
• Testing the expansion of a graph
• Testing triangle-freeness in general graphs
• Testing versus estimation of graph properties
• The complexity of promise problems with applications to public-key cryptography
• Three theorems regarding testing graph properties
• Tight Bounds for Testing Bipartiteness in General Graphs
• Tolerant property testing and distance approximation

Cited in

(11)

• Testing Lipschitz functions on hypergrid domains
• scientific article; zbMATH DE number 2156274 (Why is no real title available?)
• Non-interactive proofs of proximity
• Contemplations on Testing Graph Properties
• Randomness and computation
• Erasures versus errors in local decoding and property testing
• A Brief Introduction to Property Testing
• A brief introduction to property testing
• Introduction to testing graph properties
• Testing list H-homomorphisms
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)

This page was built for publication: Introduction to testing graph properties

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