All reports by Author Lior Gishboliner:

__
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: 2

__
TR18-007
| 9th January 2018
__

Lior Gishboliner, Asaf Shapira#### A Generalized Turan Problem and its Applications

__
TR13-059
| 9th April 2013
__

Lior Gishboliner, Asaf Shapira#### Deterministic vs Non-deterministic Graph Property Testing

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 >>>

Lior Gishboliner, Asaf Shapira

Our first theorem in this papers is a hierarchy theorem for the query complexity of testing graph properties with $1$-sided error; more precisely, we show that for every super-polynomial $f$, there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$. No result of this type was previously known for ... more >>>

Lior Gishboliner, Asaf Shapira

A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P ... more >>>