  In this paper, we consider the problem of partitioning active users in a
manner that facilitates multi-access without collision. The setting is of a
noisy, synchronous, Boolean, multi-access channel where $K$ active users (out
of a total of $N$ users) seek to access. A solution to the partition problem
places each of the $N$ users in one of $K$ groups (or blocks) such that no two
active nodes are in the same block. We consider a simple, but non-trivial and
illustrative case of $K=2$ active users and study the number of steps $T$ used
to solve the partition problem. By random coding and a suboptimal decoding
scheme, we show that for any $T\geq (C_1 +\xi_1)\log N$, where $C_1$ and
$\xi_1$ are positive constants (independent of $N$), and $\xi_1$ can be
arbitrary small, the partition problem can be solved with error probability
$P_e^{(N)} \to 0$, for large $N$. Under the same scheme, we also bound $T$ from
the other direction, establishing that, for any $T \leq (C_2 - \xi_2) \log N$,
the error probability $P_e^{(N)} \to 1$ for large $N$; again $C_2$ and $\xi_2$
are constants and $\xi_2$ can be arbitrarily small. These bounds on the number
of steps are lower than the tight achievable lower-bound in terms of $T \geq
(C_g +\xi)\log N $ for group testing (in which all active users are identified,
rather than just partitioned). Thus, partitioning may prove to be a more
efficient approach for multi-access than group testing.
