A generalized Turán problem and its applications

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.

Authors

• Lior Gishboliner
• Asaf Shapira

Keywords

• generalized Turan problem
• graph property testing