Lunch Bunches

Past Lunch Bunches

What are Lunch Bunches? Lunch Bunches have been held since the department was formed in the mid-1970s. They are informal gatherings (with lunch provided!), centered around a presentation by a faculty member, visitor, student, post-doc, or other CS community member.

Tuesday, May 6, 2008
John Doyle, Caltech
12:00 pm, 74 Jorgensen

Rules of Engagement: The Architecture of Robust, Evolvable Networks
Biological systems are robust and evolvable in the face of even large changes in environment and system components, yet can simultaneously be extremely fragile to small perturbations. Such universally robust yet fragile (RYF) complexity is found wherever we look. The amazing evolution of microbes into humans (robustness of lineages on long timescales) is punctuated by mass extinctions (extreme fragility). Diabetes, obesity, cancer, and autoimmune diseases are side-effects of biological control and compensatory mechanisms so robust as to normally go unnoticed. RYF complexity is not confined to biology. The complexity of technology is exploding around us, but in ways that remain largely hidden. Modern institutions and technologies facilitate robustness and accelerate evolution, but enable catastrophes on a scale unimaginable without them (from network and market crashes to war, epidemics, and global warming). Understanding RYF means understanding architecture — the most universal, high-level, persistent elements of organization — and protocols. Protocols define how diverse modules interact, and architecture defines how sets of protocols are organized.

Insights into the architectural and organizational principles of networked systems can be drawn from three converging research themes. 1) With molecular biology’s description of components and growing attention to systems biology, the organizational principles of biological networks are becoming increasingly apparent. Biologists are articulating richly detailed explanations of biological complexity, robustness, and evolvability that point to universal principles. 2) Advanced technology’s complexity is now approaching biology’s. While the components differ, there is striking convergence at the network level of architecture and the role of layering, protocols, and feedback control in structuring complex multiscale modularity. New theories of the Internet and related networking technologies have led to test and deployment of new protocols for high performance networking. 3) A new mathematical framework for the study of complex networks suggests that this apparent network-level evolutionary convergence within/between biology/technology is not accidental, but follows necessarily from the universal system requirements to be efficient, adaptive, evolvable, and robust to perturbations in their environment and component parts.

Tuesday, April 29, 2008
Krishna Palem, Rice University
12:00 pm, 74 Jorgensen

What To Do About The End of Moore's Law (Probably)?
Many claim that the laws of physics dictating the exponentially improving benefits of Moore’s Law will end in the next 10 to 20 years. The argument for the end of Moore’s Law is based, in part, on an analysis that switching devices cannot function deterministically as feature sizes get reduced to molecular levels. Moore’s Law could, however, continue provided systems with probabilistic switches could process information usefully. My research suggests that this is indeed possible in contexts where the "quality" of the results of the computation is perceptually determined by our senses—audio and video information being significant examples. To demonstrate this principle, I will show how CMOS-based devices, circuits and computing architectures whose correctness is characterized probabilistically can be used effectively. I will show that significant (a multiplicative factor of 2 or more) energy and performance gains can be achieved, while trading a perceptually tolerable level of error—through probabilistic adders and multipliers, applied in the context of finite impulse response filters and FFT engines processing video and audio data in digital signal processing. Quantifying the human tolerance for error, we expect, will be ultimately based on neurobiological models. Conceptually, our thesis recommending tolerating error in the switching devices in return for savings in cost, is analogous to a parametric extension of Simon's notion if satisficing—we will conclude the talk by dwelling on this analog and its implications to probabilistic design of ultra large-scale integrated (ULSI) circuits in the future.

Tuesday, April 22, 2008
Tom Heaton, Caltech Prof. of Engineering Seismology
12:00 pm, 74 Jorgensen

Designing the Next Generation of Seismographic Network
I will briefly describe the design and capabilities of the Southern California Seismic Network that is a cooperative project of Caltech’s Seismological Laboratory and the U.S. Geological Survey. This network consists of several hundred digital stations that continuously telemeter data to a central site for processing and archival. The current technology allows rapid access to widely distributed ground motion information over an extremely wide range of amplitudes (200 dB) and frequencies (30 to 0.001 Hz). However, the relatively small number of stations means that is not possible to observe unaliased seismic wavefields in either the ground or buildings. I will discuss the possibility of increasing the spatial density of seismographic stations in southern California by several orders of magnitude. This involves development of a distributed seismic network where instruments are maintained by affiliated agencies and individuals

Tuesday, April 15, 2008
Chris Umans, Caltech, Computer Science
12:00 pm, 74 Jorgensen

Randomness and Pseudorandomness: The Computational Perspective
Computational complexity views randomness as a resource to be conserved, much like running time or storage space, while "pseudo-randomness" is defined in terms of fooling a computationally-bounded observer. These unique persepectives lead to a number of widely applicable and powerful techniques, and form the basis for one of the most active areas of complexity theory.

In this talk I'll give a tour of some of these techniques -- randomness-efficient sampling, explicit constructions, and pseudo-random generators -- with example applications in game theory, coding theory, data structures, and complexity.

Tuesday, April 8, 2008
Shankar Kalyanaraman, CS Graduate Student, Caltech
12:00 pm, 74 Jorgensen

It Is (NP-)Hard To Rationalize Marriages
Given a set of observed economic choices, can one infer preferences and/or utility functions for the players that are consistent with the data? Questions of this type are called rationalization or revealed preference problems in the economic literature, and are the subject of a rich body of work.

From the computer science perspective, it is natural to study the complexity of rationalization in various scenarios. We consider a class of rationalization problems in which the economic data is expressed by a collection of matchings, and the question is whether there exist preference orderings for the nodes under which all the matchings are stable.

We show that the rationalization problem for one-one matchings is NP-complete. We propose two natural notions of approximation, and show that the problem is hard to approximate to within a constant factor, under both. On the positive side, we describe a simple algorithm that achieves a 3/4-approximation ratio for one of these approximation notions. We also prove similar results for a version of many-one matching.

Tuesday, April 1, 2008
Azita Emami, Assistant Professor of Electrical Engineering, Caltech
12:00 pm, 74 Jorgensen

High-speed Interconnects in Modern VLSI Systems
The implementation of high-performance computing systems strongly relies on the feasibility of high-bandwidth data communication between integrated circuit components (IC's). Moreover, future multi-core processors will need fast and robust intra-chip data transfer between the cores and memory units. Current trends of digital systems indicate that the amount of processing of each component or unit is expected to continue to increase exponentially at least for the next 10 years. In order to scale the communication bandwidth with the same trend, both the number of IO's and the data-rate per IO link need to increase. A number of limitations such as the bandwidth of the wires, area and power consumption per IO, interferences, and characteristics of the highly scaled devices make the design of high-speed IO's very difficult.

This talk will focus on low-power system and circuit solutions for parallel chip-to-chip interconnections and intra-chip networks. As the data-rates over the conventional wires increase, the complexity of required equalization and coding schemes increase rapidly. The design challenges of wireline data communication and the possibility of using optics for interconnection at short distances will be discussed. We will focus on a number of novel low-power solutions for both electrical and optical signaling, and the scaling properties these solutions for the future systems.

| top |