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)?


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).

  • $\begingroup$ 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? $\endgroup$ Mar 31, 2013 at 12:50
  • $\begingroup$ 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. $\endgroup$ Apr 10, 2013 at 20:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.