Testing graphs against an unknown distribution

DOI10.1007/s11856-021-2228-8zbMath1487.05258arXiv1905.09903OpenAlexW3209035668MaRDI QIDQ2130521

Asaf Shapira, Lior Gishboliner

Publication date: 25 April 2022

Published in: Israel Journal of Mathematics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1905.09903

zbMATH Keywords

graph property testingfast randomized algorithmsproperty testing modeldistribution-free testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Randomized algorithms (68W20)

Related Items (3)

Local-vs-global combinatorics ⋮ Average Gromov hyperbolicity and the Parisi ansatz ⋮ Turán and Ramsey numbers in linear triple systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing properties of graphs and functions
• Self-testing/correcting with applications to numerical problems
• Bounds for graph regularity and removal lemmas
• A weighted regularity lemma with applications
• Efficient removal without efficient regularity
• Graph removal lemmas
• On Proximity-Oblivious Testing
• Testability and repair of hereditary hypergraph properties
• Property testing and its connection to learning and approximation
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Every Monotone Graph Property Is Testable
• A theory of the learnable
• Three theorems regarding testing graph properties
• Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions
• Distribution-free Junta Testing
• Robust Characterizations of Polynomials with Applications to Program Testing
• A Wowzer-type lower bound for the strong regularity lemma
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Testing graphs in vertex-distribution-free models
• Easily Testable Graph Properties
• Introduction to Property Testing
• Testing Graph Blow-Up
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Efficient testing of large graphs
• Property testing in bounded degree graphs

This page was built for publication: Testing graphs against an unknown distribution