Algorithmic aspects of property testing in the dense graphs model

DOI10.1137/090749621MaRDI QIDQ5892636zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Dana Ron

Publication date 29 July 2011

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

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

zbMATH Keywords

adaptivity versus nonadaptivitygraph propertiesproperty testing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• On the benefits of adaptivity in property testing of dense graphs
• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers

Cited in

(12)

• An adaptivity hierarchy theorem for property testing
• Two-sided error proximity oblivious testing
• Testing Odd-Cycle-Freeness in Boolean Functions
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Test dense subgraphs in sparse uniform hypergraph
• Testing odd-cycle-freeness in Boolean functions
• Testing graph blow-up
• Testing graph blow-up
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• On the benefits of adaptivity in property testing of dense graphs
• Testing graph properties with the container method

This page was built for publication: Algorithmic aspects of property testing in the dense graphs model

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