<p>Let <span class="math-container">$A,B,C$</span> be subsets of a nonabelian group <span class="math-container">$G$</span>,
and assume we know the structure of <span class="math-container">$G$</span> &quot;fairly well&quot;
(e.g., <span class="math-container">$G = S_n$</span> or <span class="math-container">$A_n$</span>).
Assume that group operations take <span class="math-container">$O(1)$</span> time.</p>
<blockquote>
<p>Is it possible to check whether <span class="math-container">$AB \cap C \ne \emptyset$</span> in <span class="math-container">$o(|A| |B| + |C|)$</span> time
(ideally quasilinear)?</p>
</blockquote>
<h3>Motivation:</h3>
<p>A quasilinear time algorithm would produce
a roughly <span class="math-container">$O(|G|^{1/3})$</span> time algorithm for shortest paths in certain Cayley graphs
(<a href="https://math.stackexchange.com/questions/341471/computing-shortest-paths-in-cayley-graphs">if they are expanders</a>).</p>

CC BY-SA 3.0
2013-03-31T12:50:45.327Z
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
CC BY-SA 3.0
2013-04-10T20:45:02.690Z
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
CC BY-SA 4.0
2024-06-26T14:14:06.823Z
What is known about short path algorithms search on Cayley graphs ?
Alexander Chervov
<cc.complexity-theory><ds.algorithms><gr.group-theory>
Complexity of checking if AB intersects C
Geoffrey Irving
# Complexity of checking if AB intersects C

(Asked by: username_0 on 2013-03-27)

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](https://math.stackexchange.com/questions/341471/computing-shortest-paths-in-cayley-graphs)).

**Tags:** cc.complexity-theory, ds.algorithms, gr.group-theory
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: What is known about short path algorithms search on Cayley graphs ?  

---

## 0 answers

