Constant time testability of first-order logic with modulo counting on finitary graphs
This paper studies algorithmic meta theorems for property testing with \emph{constant running time} in the bounded degree model. In (Adler, Harwath 2018) it was shown that on graph classes $\mathcal C^{w}_d$ consisting of all graphs with both degree at most $d$ and treewidth at most $w$, every problem expressible in monadic second-order logic with counting (CMSO) is testable with \emph{polylogarithmic} running time (where $d,w\in \mathbb N$ are fixed). It was left open whether this can be improved to \emph{constant} running time. In this paper we give a positive answer for testing CMSO on…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.10841
curl -X POST /api/v1/records/arxiv/2605.10841/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.10841/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'