High-Speed Complex Systems: Harnessing Core Structures and Randomness

Tuesday, April 07, 2009
7:00 PM
Free and open to the public

Communication paradigms and statistical evaluation methods 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.

x x


Lara Dolecek

Postdoctoral researcher