Testing graphs in vertex-distribution-free models

DOI10.1145/3313276.3316302MaRDI QIDQ5212794zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 30 January 2020

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

Full work available at URL https://doi.org/10.1145/3313276.3316302

zbMATH Keywords

graph algorithmsone-sided vs two-sided errorproperty testing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Distribution-free connectivity testing for sparse graphs
• scientific article; zbMATH DE number 1241385

Cited in

(7)

• Permutation Tests for Infection Graphs
• Flexible Models for Testing Graph Properties
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Power of edge exclusion tests in graphical Gaussian models
• Local-vs-global combinatorics
• Distribution-free proofs of proximity
• Distribution-free connectivity testing for sparse graphs

This page was built for publication: Testing graphs in vertex-distribution-free models

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