<br>
<br>

{.title}
Testing $H$-freeness on sparse graphs, the case of bounded expansion

<br>
<br>
<br>
<br>

{.author}
<u>Samuel Humeau</u>, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny.

{.title-metadata}
> STACS 2026
>
> ENS de Lyon, LIP, équipe PLUME

<br>

{.date}
10/03/2026

{pause up #intro unreveal="sp ap ho"}
# Introduction

{#property-testing-definition}
**Property testing** is concerned with the design of [**super-fast**]{#sp} algorithms for [**approximate**]{#ap}
decision making [for **huge** objects.]{#ho}

> {pause carousel #tester-drawing}
> ----
> > ![](dessins/algo_basic.svg)
> ---
> > ![](dessins/algo_huge.svg)
> ---
> > ![](dessins/algo_memory.svg)
> ---
> > ![](dessins/algo_queries.svg)
> ---
> > ![](dessins/algo_queries_number.svg)
> ---
> > ![](dessins/algo_approx.svg)
> ---
> > ![](dessins/algo_representation.svg)
> ---
> > ![](dessins/algo_tester.svg)
> ---
> > ![](dessins/algo_output.svg)
> ---
> > ![](dessins/algo_queries_complexity.svg)

{reveal="ho"}

{change-page="tester-drawing"}

{change-page="tester-drawing"}

{change-page="tester-drawing"}

{reveal="sp"}

{change-page="tester-drawing"}

{reveal="ap"}

{change-page="tester-drawing"}

{pause #focus-drawing}
Algorithm **correct** w.h.p on instances: {pause}
- Satisfying $P$, {pause}
- **Far** from satisfying $P$.

{pause}
Property testing is a theory of **sublinear** algorithms.

{pause up="property-testing-definition"}
Seminal papers:
- Blum, Luby, and Rubinfeld (1990), {pause}
- Goldreich, Goldwasser, and Ron (1998).