The induced C4C_4-freeness polynomial testability conjecture

From papers

Let C4C_4 denote the cycle with four vertices, and let qind-C4-free(ε)q_{\text{ind-}C_4\text{-free}}(\varepsilon) be the query complexity for testing induced C4C_4-freeness. Induced C4C_4-freeness conjecture.

qind-C4-free(ε)=poly(1/ε).q_{\text{ind-} C_4\text{-free}}(\varepsilon)=\operatorname{poly}(1/\varepsilon).

This is the remaining case in the characterization of graphs with polynomially testable induced-freeness, following the known results for the other graphs.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Lior Gishboliner and Asaf Shapira, “Polynomial Property Testing”, arXiv:2508.16878 (2025).

Solutions 0

No solutions have been posted yet.