# Complexity of checking if AB intersects C

Let $$A,B,C$$ be subsets of a nonabelian group $$G$$, and assume we know the structure of $$G$$ "fairly well" (e.g., $$G = S_n$$ or $$A_n$$). Assume that group operations take $$O(1)$$ time.

Is it possible to check whether $$AB \cap C \ne \emptyset$$ in $$o(|A| |B| + |C|)$$ time (ideally quasilinear)?

### Motivation:

A quasilinear time algorithm would produce a roughly $$O(|G|^{1/3})$$ time algorithm for shortest paths in certain Cayley graphs (if they are expanders).

• If $A$, $B$, and $C$ can be any subset of $G$, why should $G$ being a group help? Is something known about the abelian case? – Tyson Williams Mar 31 '13 at 12:50
• It's quite possible that it doesn't. The abelian case where $|A|,|B| = \Theta(|G|)$ can be solved via Fourier transform, but I don't know how to do small subsets. – Geoffrey Irving Apr 10 '13 at 20:45