We present a novel decoding scheme for slotted ALOHA which is based on concepts from physical-layer network coding (PNC) and multi-user detection (MUD). In addition to recovering individual user packets from a packet collision as it is usually done with MUD, the receiver applies PNC to decode packet combinations that can be used to retrieve the original packets using information available from other slots. We evaluate the novel scheme and compare it with another scheme based on PNC that has been proposed recently and show that both attain important gains compared to basic successive interference cancellation. This suggests that combining PNC and MUD can lead to significant gains with respect to previously proposed methods on either one or the other. I. INTRODUCTION In a random multiple-access scheme, various users access the same channel with no or very limited coordination which may result in packet collisions. In contrast to demand assign- ment multiple-access (DAMA) schemes, in which collisions are avoided by pre-allocating the radio resources to the users, in random multiple-access protocols, such as e.g. ALOHA, packet collisions cannot be avoided due to the lack of co- ordination. Such uncoordinated multiple-access protocols are preferable over scheduled access in various scenarios including • systems with long inherent feedback delay, e.g. satellite networks