8
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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$
    – Tyson Williams
    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$
    – Geoffrey Irving
    Apr 10, 2013 at 20:45

0

Reset to default

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.