Partial associativity and rough approximate groups

Let X be a set of size n with a binary operation on it such that the associative property a(bc) = (ab)c holds for at least cn^3 triples (a,b,c). What can one say about such an operation? In particular, must there be some group hiding in the background that "explains" all the associativity? This question has obvious similarities to questions in additive combinatorics such as what one can say about sets A of integers that contain many quadruples (a,b,c,d) with a+b=c+d. A key tool for answering such questions is the Balog-Szemerédi theorem. I shall talk about recent work with Jason Long in which we show that the multiplication table of a binary operation with many associative triples must approximately agree on a dense set with part of the multiplication table of a metric group. A natural stronger statement — that it must agree on a dense set with part of the multiplication table of a group — was recently shown to be false by Ben Green, so our result is in a certain sense the best one can hope for. Our proof methods (which are much to complicated to present in detail in a one-hour talk) make heavy use of dependent random selection, which can also be used to prove the Balog-Szemerédi theorem.