New Approaches in Large Systems: Theory and Algorithms

Speaker: Chandra Nair, Microsoft ResearchAbstract: This talk will contain two parts: The dominant part, as the title suggests, will be about a novel and exciting interplay between various disciplines that has led to new approaches to solve problems in large systems. The second part will address a very well-known information theoretic open problem, i.e. determining the capacity region of a broadcast channel, and I shall present new outer bounds on the set of achievable rates that supersede the existing best known outer bounds.Large systems such as internet, large error correcting codes, gene networks, etc. present a new class of problems that are different from the traditional optimization problems in smaller systems. Instead of seeking exact answers, one is often satisfied with very good approximations that can be computed in an efficient, distributed and robust manner. Further due to the presence of a large system of interacting objects one also expects some generic macroscopic behavior to emerge. These constraints and effects are quite different from the behavior or premises under which the smaller systems have been studied and hence the traditional approaches are insufficient.Over the past few years new approaches from Spin Glass Theory, a branch of statistical physics, have been used to propose solutions and efficient algorithms for hard optimization problems in Electrical Engineering, Computer Science, and more recently in Biological networks. This talk will overview this interplay and focus on some examples: (i) The Random Assignment Problem (RAP), which arises in a variety of practical scenarios; notably in crossbar switch scheduling.
(ii) The Number Partitioning Problem (NPP), which models load balancing and multiprocessor scheduling.
(iii) Designing exact message passing algorithms on loopy graphs.In the first two examples listed above, I shall overview the resolutions of certain conjectures in these problems, conjectures that were motivated by heuristic arguments from Physics.In the second part of the talk, I will address a very traditional problem in multi-user information theory. This concerns obtaining the capacity region of a system with one transmitter and two receivers with private messages, called the broadcast channel, a problem that is still open. In this talk, I will show a new outer bound that is better than the previously best known outer bound due to Korner and Marton (1979).Biography: Chandra Nair is a Post-Doctoral researcher with the theory group at Microsoft Research, Redmond. He obtained his PhD from the Electrical Engineering Department at Stanford University in June 2005. He obtained the Bachelor's degree in Electrical Engineering from IIT, Madras. His research interests are in developing and applying tools from probability, combinatorics and statistical physics to solve discrete optimization problems that arise in large systems, esp. those in Electrical Engineering, Computer Science and very recently, in biological systems. He is also interested in information theory, algorithm design, and networks. He has received the Stanford Graduate Fellowship(2000-2004) and Microsoft Graduate Fellowship(2004-2005) for his graduate studies, and he was awarded the Philips and Siemens(India) Prizes for his undergraduate studies.Host: Giuseppe Caire, caire@usc.edu

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos