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

DOI10.1137/23M1556253MaRDI QIDQ6573776zbMATH OpenFDO

Authors Isolde Adler, Noleen Köhler, Pan Peng

Publication date 17 July 2024

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

zbMATH Keywords

lower boundfirst-order logiclocalitygraph property testingproximity-oblivious testing

Mathematics Subject Classification ID

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)