All reports by Author Asaf Shapira:

__
TR20-177
| 12th October 2020
__

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira#### Counting Subgraphs in Degenerate Graphs

__
TR20-107
| 19th July 2020
__

Lior Gishboliner, Asaf Shapira, Henrique Stagni#### Testing linear inequalities of subgraph statistics

__
TR19-083
| 4th June 2019
__

Lior Gishboliner, Asaf Shapira#### Testing Graphs against an Unknown Distribution

Revisions: 1

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has {\em bounded degeneracy}. ... more >>>

Lior Gishboliner, Asaf Shapira, Henrique Stagni

Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property ${\cal P}$ and those that are far from satisfying it. Since these algorithms operate by inspecting a small randomly selected portion of the input, the most natural property one would like to be ... more >>>

Lior Gishboliner, Asaf Shapira

The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graphâ€™s vertex set. A graph property $\mathcal{P}$ is said ... more >>>