## Abstract

Our first theorem in this paper is a hierarchy theorem for the query complexity of testing graph properties with 1-sided error; more precisely, we show that for every sufficiently fast-growing function f , there is a graph property whose 1-sided-error query complexity is precisely f (Θ(1/)). No result of this type was previously known for any f which is super-polynomial. Goldreich [ECCC 2005] asked to exhibit a graph property whose query complexity is 2^{Θ}(1/ε). Our hierarchy theorem partially resolves this problem by exhibiting a property whose 1-sided-error query complexity is 2^{Θ}(1/ε). We also use our hierarchy theorem in order to resolve a problem raised by the second author and Alon [STOC 2005] regarding testing relaxed versions of bipartiteness. Our second theorem States that for any function f there is a graph property whose 1-sided-error query complexity is f (Θ(1/)) while its 2-sided-error query complexity is only poly(1/). This is the first indication of the surprising power that 2-sided-error testing algorithms have over 1-sided-error ones, even when restricted to properties that are testable with 1-sided error. Again, no result of this type was previously known for any f that is super polynomial. The above theorems are derived from a graph theoretic result which we think is of independent interest, and might have further applications. Alon and Shikhelman [JCTB 2016] introduced the following generalized Turán problem: for fixed graphs H andT, and an integer n, what is the maximum number of copies of T, denoted by ex(n,T, H), that can appear in an n-vertex H-free graph? This problem received a lot of attention recently, with an emphasis on ex(n,C_{3},C_{2}ℓ+_{1}). Our third theorem in this paper gives tight bounds for ex(n,C_{k},C_{ℓ}) for all the remaining values of k and ℓ.

Original language | English |
---|---|

Title of host publication | STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Monika Henzinger, David Kempe, Ilias Diakonikolas |

Publisher | Association for Computing Machinery |

Pages | 376-389 |

Number of pages | 14 |

ISBN (Electronic) | 9781450355599 |

DOIs | |

State | Published - 20 Jun 2018 |

Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|

Country/Territory | United States |

City | Los Angeles |

Period | 25/06/18 → 29/06/18 |

### Funding

Funders | Funder number |
---|---|

Horizon 2020 Framework Programme | 633509 |

## Keywords

- Generalized turán problem
- Graph property testing