The emergence of networks of many devices in the context of cyber-physical systems underscores the need for novel solutions for communication over random access channels. Most protocols currently in place rely on collision avoidance and are woefully ill-suited to handling high variation in the number and variety of communicators. We ask the question of whether it is possible, in a scenario where no one knows how many transmitters are active, for the receiver to almost always recover the messages sent by all active transmitters. Surprisingly, we find that not only is reliable decoding possible in this regime, but it is possible to attain both the capacity and the dispersion of the multiple access channel in operation. Our strategy relies on ''semi-rateless'' codes: decoding attempts are made at a sparse set of pre-determined decoding times, and the decoder is tasked with recovering from the channel output the messages of the active transmitters. Once the decoder determines that reliable decoding can be made, a positive acknowledgement (ACK) is sent to the encoders, indicating the end of that communication epoch and the start of a new one. The feedback ensures that the collection of active transmitters remains fixed during each epoch. These semi-rateless codes work for both channel and source coding; for source coding, our semi-rateless scheme achieves the optimal performance up to the first three order terms in the Gaussian approximation of the optimal rate. The analysis includes a refinement of the random coding argument ensuring the existence of a deterministic code that meets multiple constraints simultaneously, a random-coding union achievability bound for multiple access, and a sharp converse bound for multiple access source coding via a connection to composite hypothesis testing.
Based on joint works (ArXiv:1801.09018, ArXiv:1902.03366) with M. Effros, R. C. Yavas, S. Chen.
Victoria Kostina joined Caltech as an Assistant Professor of Electrical Engineering in the fall of 2014. She holds a Bachelor's degree from Moscow institute of Physics and Technology (2004), where she was affiliated with the Institute for Information Transmission Problems of the Russian Academy of Sciences, a Master's degree from University of Ottawa (2006), and a PhD from Princeton University (2013). She received the Natural Sciences and Engineering Research Council of Canada postgraduate scholarship (2009--2012), the Princeton Electrical Engineering Best Dissertation Award (2013), the Simons-Berkeley research fellowship (2015) and the NSF CAREER award (2017). Kostina's research spans information theory, coding, control and communications.