  Obtaining an efficient bound for the triangle removal lemma is one of the
most outstanding open problems of extremal combinatorics. Perhaps the main
bottleneck for achieving this goal is that triangle-free graphs can be highly
unstructured. For example, triangle-free graphs might have only regular
partitions (in the sense of Szemer\'edi) of tower-type size. And indeed,
essentially all the graph properties ${\cal P}$ for which removal lemmas with
reasonable bounds were obtained, are such that every graph satisfying ${\cal
P}$ has a small regular partition. So in some sense, a barrier for obtaining an
efficient removal lemma for property ${\cal P}$ was having an efficient
regularity lemma for graphs satisfying ${\cal P}$.
  In this paper we consider the property of being induced $C_4$-free, which
also suffers from the fact that a graph might satisfy this property but still
have only regular partitions of tower-type size. By developing a new approach
for this problem we manage to overcome this barrier and thus obtain a merely
exponential bound for the induced $C_4$ removal lemma. We thus obtain the first
efficient removal lemma that does not rely on an efficient version of the
regularity lemma. This is the first substantial progress on a problem raised by
Alon in 2001, and more recently by Alon, Conlon and Fox.

Combinatorics