How to achieve global results via local action? This, in essence, is the underlying challenge in many problems in modern information systems. Belief Propagation (BP) has enjoyed tremendous empirical success in broadly addressing this challenge, in a diverse array of applications: image processing, decoding of channel codes, machine learning, statistical physics etc.
However, BP is a heuristic; the lack of precise guarantees on its performance stands in stark contrast to its empirical success. In this talk we expand the analytical understanding of BP, and widen its applicability, by investigating its performance in a new domain: networking.
We first motivate how the fundamental structure of many networking problems makes BP a natural fit for these problems, by focusing on three specific applications: wireless scheduling, sensor network self-organization, and resource allocation. We highlight its algorithmic simplicity, and demonstrate its empirical performance.
We then show that the setting of networking problems allows for a deeper insight into BP itself. At the core of our networking applications lie canonical combinatorial problems: weighted matching and independent set. Our analysis reveals that, for these problems, BP is precisely a fast distributed implementation of linear programming. This insight has the potential to foster even better algorithms for the large spectrum of applications that BP is already applied to. We also demonstrate the first use of BP as a proof technique, using our analysis to establish fundamental structural properties of random instances of weighted independent set problems.
In conclusion, we comment on the potential of BP as a generic framework for distributed algorithms, on adapting it for new applications, and on the need for a richer exchange of ideas between the fields of communications and statistical learning and inference.
Sujay Sanghavi received his B. Tech in Electrical Engineering from IIT Bombay, after which he joined the University of Illinois, Urbana-Champaign. There he received an MS in Mathematics, and an MS and PhD in Electrical Engineering. Sujay's graduate research focused on communication networks, under the advice of Bruce Hajek. After graduating, Sujay joined MIT as a postdoc in Alan Willsky's group, where he works on large-scale statistical inference and machine learning, and on their interactions with networking and communications.
Sujay's primary research interest is the development and analysis of large-scale distributed algorithms for modern information systems, using tools from probability, optimization and combinatorics. He was a recipient of the Perry award in 2002, and the Mavis award in 2005, while at UIUC.