DOI10.1002/rsa.10078zbMath1048.68062OpenAlexW2139374679WikidataQ105583190 ScholiaQ105583190MaRDI QIDQ4417002
Oded Goldreich, Luca Trevisan
Publication date: 6 August 2003
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.10078
Testing graphs against an unknown distribution,
Testing Odd-Cycle-Freeness in Boolean Functions,
An adaptivity hierarchy theorem for property testing,
Fast Property Testing and Metrics for Permutations,
Densities in large permutations and parameter testing,
Finding cycles and trees in sublinear time,
On the benefits of adaptivity in property testing of dense graphs,
Two new perspectives on multi-stage group testing,
On the Effect of the Proximity Parameter on Property Testers,
Flexible Models for Testing Graph Properties,
Testing linear inequalities of subgraph statistics,
Indistinguishability and First-Order Logic,
Hypergraph regularity and random sampling,
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification,
Easily Testable Graph Properties,
Hierarchy theorems for property testing,
Unnamed Item,
Unnamed Item,
Algorithmic Aspects of Property Testing in the Dense Graphs Model,
Introduction to Testing Graph Properties,
Distribution-free connectivity testing for sparse graphs,
Distributed discovery of large near-cliques,
Deterministic vs non-deterministic graph property testing,
Hierarchy Theorems for Property Testing,
A separation theorem in property testing,
Testing permutation properties through subpermutations,
\(\omega\)-regular languages are testable with a constant number of queries,
Fast distributed algorithms for testing graph properties,
Earthmover Resilience and Testing in Ordered Structures,
Two-sided error proximity oblivious testing,
Testing subgraphs in directed graphs,
Testing Graph Blow-Up,
Testing Graph Blow-Up,
Proximity Oblivious Testing and the Role of Invariances,
Proximity Oblivious Testing and the Role of Invariances,
On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs,
A Canonical Form for Testing Boolean Function Properties,
Inflatable Graph Properties and Natural Property Tests,
On the Average-Case Complexity of Property Testing,
Introduction to Testing Graph Properties,
Contemplations on Testing Graph Properties,
A unified framework for testing linear‐invariant properties,
A characterization of constant‐sample testable properties,
On the Query Complexity of Estimating the Distance to Hereditary Graph Properties,
Estimating parameters associated with monotone properties,
Unnamed Item,
Lower bounds for testing triangle-freeness in Boolean functions
