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) Logic in computer science (03B70) Randomized algorithms (68W20)

Cites Work

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

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)