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

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

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)