Theory Seminar, Wednesday Dec 31: Reut Levi (Reichman) - Tolerant Testers for Subgraph-Freeness

[Arnold Filtser]

Hi all,

Next week (Wed Dec 31, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

Looking forward to seeing you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Reut Levi (Reichman)
Title: Tolerant Testers for Subgraph-Freeness
Abstract:  In this paper we study the problem of tolerantly test the property of being $H$-free (which also implies distance approximation from being $H$-free).
   
In the general-graphs model, we show that for tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $\Omega(1))$.

Specifically for triangles, our algorithm distinguished graphs which are $\epsilon$-close to being triangle-free from graphs that $3\epsilon(1+\eta)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $\eta$ and $\epsilon$).
       
For general $k$-cliques our algorithm distinguishes graphs which are $\epsilon$-close to being $K_k$-free from graphs which are ${k \choose 2}\epsilon(1+\eta)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $\epsilon$, $\gamma$ and $arb(G)$.

We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected of radius $1$. This includes for example the wheel-graph.

Finally, we show that our tester can be applied to the bounded-degree model for tolerantly test $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.

Joint work with Jonathan Meiri.

[Arnold Filtser]

The seminar starts in one hour!