Faster Property Testers in a Variation of the Bounded Degree Model

DOI10.1145/3584948arXiv2009.07770OpenAlexW3085282378MaRDI QIDQ6116363

Unnamed Author, Isolde Adler

Publication date: 18 July 2023

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.07770

zbMATH Keywords

property testingbounded degree modellogic and databasesconstant time algorithms

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Every minor-closed property of sparse graphs is testable
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Parametrized complexity theory.
• Every Property of Hyperfinite Graphs Is Testable
• Property Testing for Bounded Degree Databases
• Testing Triangle-Freeness in General Graphs
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• Answering FO+MOD Queries under Updates on Bounded Degree Databases
• Local Graph Partitions for Approximation and Testing
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• First-order queries on structures of bounded degree are computable with constant delay
• On spectra of sentences of monadic second order logic with counting
• On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs *
• Efficient testing of large graphs
• Property testing in bounded degree graphs

This page was built for publication: Faster Property Testers in a Variation of the Bounded Degree Model