Algorithmic Structures for Uncoordinated Communications and Statistical Inference in Exceedingly Large Spaces (24w5280)


(Columbia University)

Jean-Francois Chamberland (Texas A&M University)

Victoria Kostina (Caltech)


(University of Toronto)


The Banff International Research Station will host the “Algorithmic Structures for Unsourced Communications and Statistical Inference in Exceedingly Large Spaces” workshop in Banff from March 10 - 15, 2024.

This workshop aims at enabling the creation of novel algorithmic structures attuned to unsourced communications and inference in exceedingly large dimensional spaces. This, in turn, will be used as a foundation to devise new wireless access schemes for machine-driven data transfers. The impetus behind this research program is a realization that wireless traffic is increasingly heterogeneous, with growth coming primarily from unattended devices. This represents a formidable challenge for current infrastructures because these devices interact with the Internet in fundamentally different ways than humans. Specifically, humans tend to establish sustained Internet connections while interacting with their phones or computers, and they transfer large amounts of data. Access points have been designed and deployed to support typical human densities and traffic patterns. Machines and IoT devices, on the other hand, often transmit status updates or control decisions with very short payloads in a sporadic manner. And, their density is poised to skyrocket over the next few years, reaching orders of magnitudes beyond that of humans. This emerging digital landscape is ill-matched with current architectures, as it is incompatible with the traditional acquisition-estimation-scheduling paradigm found in existing systems. Without a fundamental redesign of wireless systems, the inability of wireless infrastructures to efficiently carry machine-type traffic will act as a bottleneck for growth and innovation. A recently proposed means to address this shortcoming is to introduce wireless schemes tailored to communication with small payloads and sporadic, bursty traffic. Key attributes of the envisioned architecture include random access and the ability to operate without explicitly acquiring device identities. This significant departure from past paradigm is crucial in eliminating the need for individualized feedback, which enabled high-throughput connections in the past, yet is rapidly becoming cost-prohibitive as a mechanism for machine-type data transfers.

The mathematical underpinnings of this new viewpoint are closely related to compressed sensing in very large dimensions. As such, prospective research directions are informed by the many recent advances in this area. Yet, the dimensionality of the problems to be solved for machine-type communication far exceed the capabilities of commodity compressed sensing solvers. New frameworks and efficient algorithms have to be created. This field of study thus addresses a timely engineering challenge and, concurrently, pushes the boundary of knowledge in the area of inference in spaces with exceedingly large dimensions. In addressing various aspects of this problem, we anticipate tools from various areas to play key roles, including finite-blocklength information theory, statistical physics, and iterative methods, and compressed sensing. In this sense, the workshop offers a unique opportunity for cross-fertilization across loosely related fields, while addressing a pertinent societal need.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada’s Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta’s Advanced Education and Technology, and Mexico’s Consejo Nacional de Ciencia y Tecnología (CONACYT).