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:

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