Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Asaf Shapira:

TR20-177 | 12th October 2020
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

Counting Subgraphs in Degenerate Graphs

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

TR20-107 | 19th July 2020
Lior Gishboliner, Asaf Shapira, Henrique Stagni

Testing linear inequalities of subgraph statistics

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

TR19-083 | 4th June 2019
Lior Gishboliner, Asaf Shapira

Testing Graphs against an Unknown Distribution

Revisions: 1

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

ISSN 1433-8092 | Imprint