LAUSR

The problem of computing the modulo-sum of independent messages over a finite-field erasure multiple access channel is investigated. The focus is on the role of delayed state feedback for function computation over state dependent multiple access channels. For the two-user case, a set of new outer bounds on the non-feedback computation capacity region are developed, which strictly improve the state of the art by Khisti et al., 2013. As a result, a previously unsettled question is answered in the affirmative: delayed state feedback strictly increases computation capacity for the two-user erasure multiple access channel universally. The proof leverages the subset entropy inequalities by Madiman and Tetali, 2010, Jiang et al., 2014, and submodularity of conditional entropies. For the achievability part of the non-feedback case, an achievable computation rate region is derived by generalizing the proposed schemes in Khisti et al., 2013. Beyond the two-user case, the $K$ -user case is also investigated, with emphasis on the large system regime, where $K$ is the number of users. For the non-feedback case, we propose a grouping scheme which has higher computation rate than that of the conventional “compute-and-forward” (CF) scheme. Furthermore, with a growing number of users, the proposed grouping scheme strictly outperforms the conventional “decode-and-forward (DF)” scheme when the erasure probability is smaller than $1-e^{\frac {1}{e}}\approx 0.3078$ . This is in contrast to the two-user case where the currently best known achievability (Khisti et al., 2013) coincides with the better one between DFand CF. For the case with delayed state feedback, a new hybrid-ARQ-type scheme is proposed, and in the large system regime, it achieves a computation rate scaling like $\Omega \left({\frac {1}{\log (K)}}\right)$ , much higher than the scaling $\Theta \left({\frac {1}{K}}\right)$ achieved by the grouping scheme without feedback.