Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CYCLES IN GRAPHS:
Reports tagged with cycles in graphs:
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 >>>

ISSN 1433-8092 | Imprint