High-Speed Complex Systems: Harnessing Core Structures and Randomness

April 17, 2009
3:15pm-4:00pm
414 CEPSR
Speaker: Lara Dolecek, MIT

Abstract

We are ushering into the era of ubiquitous large-scale complex systems that will offer high-speed data communication, reliable low-power data storage and efficient data inference -- all occurring on a massive scale. An indispensable step towards a systematic innovation in such high-performance systems is the identification of the appropriate performance metric, and the subsequent development of a methodology for efficient system evaluation based on this metric. I will put forth an approach based on sophisticated statistical methods that harness core system structures and the underlying randomness to produce fast and accurate system evaluation. I will discuss this approach in the context of graph-based codes that are becoming the error correcting codes of choice for most high-speed communication systems. The performance of such systems is determined by the probability of error in decoding. The key challenge in efficient evaluation and better system design arises from the dependency on the underlying iterative decoding algorithms that are practical but not well understood. I will introduce the concept of an absorbing set as the fundamental combinatorial structure for identifying dominant decoding failures: this structure redefines the conventional performance metric. A new theoretical framework based on the absorbing sets leads to a highly efficient and accurate importance sampling evaluation of graph-based codes, and moreover enables a systematic improvement of practical communication systems. By generalizing the traditional domain of communication systems to the realm of delay-sensitive complex systems, I will discuss how the proposed approach based on the information theoretic ideas of rare events coupled with the suitable fast statistical algorithms, can be successfully applied for evaluating the yield (proportion of functional devices) of nano-scale circuit systems, as well as for efficient inference in increasingly popular large-scale social networks.

Biography

Lara Dolecek is a post-doctoral researcher with the Massachusetts Institute of Technology. She holds a B.S, M.S. and Ph.D. degrees in Electrical Engineering and Computer Sciences, as well as an M.A. degree in Statistics, all from the University of California, Berkeley. For her dissertation she received the 2007 David J. Sakrison Memorial Prize for the most outstanding doctoral research in the Department of Electrical Engineering and Computer Sciences at UC Berkeley.

She also received several UC Berkeley-wide awards for her graduate research including the multi-year Eugene Cota-Robles Fellowship and the Dissertation Year Fellowship. Her research interests span information and probability theory, graphical models, combinatorics, statistical algorithms and computational methods with applications to high-performance complex systems for data processing, communication, and storage.


500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University