On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing

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

Cites Work

scientific article; zbMATH DE number 3819693 (Why is no real title available?)
scientific article; zbMATH DE number 803291 (Why is no real title available?)
scientific article; zbMATH DE number 3266604 (Why is no real title available?)
scientific article; zbMATH DE number 7788434 (Why is no real title available?)
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
An optimal construction of Hanf sentences
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
Efficient testing of large graphs
Entropy waves, the zig-zag graph product, and new constant-degree expanders
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
Every minor-closed property of sparse graphs is testable
Every property of hyperfinite graphs is testable
Expander graphs and their applications
GSF-locality is not sufficient for proximity-oblivious testing
Introduction to Property Testing
Large networks and graph limits
Local Graph Partitions for Approximation and Testing
On Proximity-Oblivious Testing
On monadic NP vs monadic co-NP
On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
Property testing and its connection to learning and approximation
Property testing for bounded degree databases
Property testing in bounded degree graphs
Property testing on \(k\)-vertex-connectivity of graphs
Proximity oblivious testing and the role of invariances
Random walks and forbidden minors II
Relating two property testing models for bounded degree directed graphs
Robust Characterizations of Polynomials with Applications to Program Testing
Self-testing/correcting with applications to numerical problems
Testing subdivision-freeness: property testing meets structural graph theory
Two-sided error proximity oblivious testing
\(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

This page was built for publication: On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing

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