Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Lior Gishboliner:

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

TR18-007 | 9th January 2018
Lior Gishboliner, Asaf Shapira

A Generalized Turan Problem and its Applications

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

TR13-059 | 9th April 2013
Lior Gishboliner, Asaf Shapira

Deterministic vs Non-deterministic Graph Property Testing

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

ISSN 1433-8092 | Imprint