  Although $S_\omega$ (the group of all permutations of $\mathbb{N}$) is size
continuum, both it and its closed subgroups can be presented as the set of
paths through a countable tree. The subgroups of $S_\omega$ that can be
presented this way with finite branching trees are exactly the profinite ones.
We use these tree presentations to find upper bounds on the complexity of the
existential theories of profinite subgroups of $S_\omega$, as well as to prove
sharpness for these bounds. These complexity results enable us to distinguish a
simple subclass of profinite groups, those with \emph{orbit independence}, for
which we find an upper bound on the complexity of the entire first order
theory.
