English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix someminor-closed property $\mathcal{P}$ (such as planarity). We say that $G$ is$\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$edges to make it have $\mathcal{P}$. The problem of property testing$\mathcal{P}$ was introduced in the seminal work of Benjamini-Schramm-Shapira(STOC 2008) that gave a tester with query complexity triply exponential in$\varepsilon^{-1}$. Levi-Ron (TALG 2015) have given the best tester to date,with a quasipolynomial (in $\varepsilon^{-1}$) query complexity. It is an openproblem to get property testers whose query complexity is$\text{poly}(d\varepsilon^{-1})$, even for planarity.  In this paper, we resolve this open question. For any minor-closed property,we give a tester with query complexity $d\cdot \text{poly}(\varepsilon^{-1})$.The previous line of work on (independent of $n$, two-sided) testers isprimarily combinatorial. Our work, on the other hand, employs techniques fromspectral graph theory. This paper is a continuation of recent work of theauthors (FOCS 2018) analyzing random walk algorithms that find forbiddenminors.

Random walks and forbidden minors II: A $\text{poly}(d\varepsilon^{-1})$-query tester for minor-closed properties of bounded-degree graphs