Introduction to Testing Graph Properties

DOI10.1007/978-3-642-22670-0_32zbMATH Open1343.68299OpenAlexW2113337364MaRDI QIDQ3088198FDOQ3088198

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing subgraphs in directed graphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Property testing and its connection to learning and approximation
• Efficient testing of large graphs
• Property testing in bounded degree graphs
• Self-testing/correcting with applications to numerical problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• lgorithmic and Analysis Techniques in Property Testing
• Computational Complexity
• MAX-CUT has a randomized approximation scheme in dense graphs
• A combinatorial characterization of the testable graph properties
• The complexity of promise problems with applications to public-key cryptography
• A sublinear bipartiteness tester for bounded degree graphs
• Three theorems regarding testing graph properties
• Approximating average parameters of graphs
• Testing subgraphs in large graphs
• Lower bounds for sampling algorithms for estimating the average
• Testing the expansion of a graph
• Testing triangle-freeness in general graphs
• Testing the diameter of graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• Tight Bounds for Testing Bipartiteness in General Graphs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Hierarchy Theorems for Property Testing
• Approximate Hypergraph Partitioning and Applications
• A separation theorem in property testing
• Local Graph Partitions for Approximation and Testing
• An Expansion Tester for Bounded Degree Graphs
• Testing \(k\)-colorability
• Every monotone graph property is testable
• Testing versus estimation of graph properties
• Tolerant property testing and distance approximation
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• A Brief Introduction to Property Testing
• Testing graph isomorphism
• On the Benefits of Adaptivity in Property Testing of Dense Graphs

Cited In (7)

• Testing Lipschitz functions on hypergrid domains
• Non-interactive proofs of proximity
• Contemplations on Testing Graph Properties
• Erasures versus errors in local decoding and property testing
• A Brief Introduction to Property Testing
• Randomness and Computation
• Testing list \(H\)-homomorphisms

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)