Tuesday, May 20, 2008
Yury Lifshits, Caltech
74 Jorgensen, 12:00 pm

The Architecture of the Web
Initially the Web was defined as a system of interlinked hypertext documents accessed via the Internet. Its structure is regulated by World Wide Web Consortium via standards like URL, HTML, CSS and RSS. The Web of 2008 is a system of data, web applications and people. Necessity of syncronization raised the next generation of standards: OpenID, OAuth, Social Graph API, Microformats and various widget platforms (F8, Open Social, Firefox, iPhone, iGoogle, Wordpress, Drupal, Salesforce.com).

We start with systematic overview of Web architecture. Then we discuss research agenda in the field: data flow (publishing, synchronization and exchange), web operating systems and identity management. Finally we present our ongoing project "New Approaches to Online Marketing".

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

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
74 Jorgensen, 12:00 pm

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
74 Jorgensen, 12:00 pm

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.
***Lunch is provided****

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

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, Caltech
74 Jorgensen, 12:00 pm

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, Caltech
74 Jorgensen, 12:00 pm

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.

Tuesday, March 18, 2008
Ulrich Pinkall, Berlin University of Technology
74 Jorgensen, 12:00 pm

What Game Engines Can Do For Mathematical Visualization
Surfaces with constant (mean or Gaussian) curvature are a classical topic in Differential Geometry. The shape of such surfaces is usually quite complex and poses a real challenge for Computer Graphics and interactive visualization. We will demonstrate that an optimal environment for doing mathematical experiments with surfaces is to put them in a virtual landscape where one can walk on the surfaces and interact with them in a way modeled after first person computer games.

Tuesday, March 11, 2008
Jeanne Holm, JPL
74 Jorgensen, 12:00 pm

Virtual Worlds and Space Exploration
Populations of virtual worlds, such as Second Life, have grown rapidly. This talk discusses using virtual worlds for bringing lots of people into the NASA mission, letting them participate in the day to day work and successes of the U.S. space agency. NASA has established several islands in Second Life. NASA CoLab and Explorer Island are the two main public entrance points. These areas are geared at working with any person who is interested in learning more about NASA or, better yet, participating in a NASA mission for exploration in this virtual world. While NASA CoLab focuses on a place to host meetings and talks, Explorer Island (created by the Jet Propulsion Laboratory) is meant to be an immersive environment for interacting with spacecraft, being at a live launch of the Space Shuttle or a mission to Mars, talking to NASA scientists and engineers, sharing your ideas for space exploration in international workshops, and walking on the surface of another world. Come in world and look for Jet Burns (Charles White) or Devery Barrymore (Jeanne Holm) and we'll give you a tour!

Tuesday, March 4, 2008
Hsuan-Tien Lin, Caltech
74 Jorgensen, 12:00 pm

From Ordinal Ranking to Binary Classification
Ordinal ranking is an important concept in modeling our preferences. We rank hotels by stars to represent their quality; we give feed-backs to products on Amazon using a scale from one to five; we say that the weather is hot, warm, cool, or cold without referring to the actual temperature. The wide applications of ranking range from social science to behavioral science to information retrieval. For yet another example, in 2006, Netflix (an on-line DVD rental company) announced a million-dollar-prize challenge for building a better automatic personalized movie ranking system, and the prize is heating up the competition in machine learning and related areas.

Many machine learning approaches are designed in recent years to understand ordinal ranking better, but the design process can be time-consuming. Our work presents a novel alternative -- a reduction framework that systematically transforms ordinal ranking to simpler yes/no questions, i.e., binary classification.

Then, well-studied binary classification approaches can be effortlessly casted as new ordinal ranking ones. Furthermore, the reduction framework reveals a strong theoretical connection between ordinal ranking and binary classification, and allows us to easily extend well-known theoretical results for binary classification to new ones for ordinal ranking. In this talk, I will discuss the intuition and the construction of the reduction framework, as well as its theoretical and algorithmic merits, using the Netflix challenge as an example.

Tuesday, February 26, 2008
Paul De Martini, Southern California Edison
74 Jorgensen, 12:00 pm

Partnering with our Customers for a Smarter, Cleaner Energy Future
SmartConnect, a new effort by Southern California Edison, will enable the utility to manage increasing demand for electricity from customers and provide environmental benefits by deploying a smart meter system which could reduce peak demand by as much as 1,000 megawatts - the output of a large power plant - as customers reduce some peak electricity usage and shift some peak usage to off-peak periods of the day when power costs less. Additional savings include lower labor costs due to the use of wireless data transfer from meters to the utility rather than manual meter reading. Paul De Martini, Director of SmartConnect, will describe the program, its development plan, and the technological challenges it faces.

Tuesday, February 19, 2008
Alex Groce & Klaus Havelund
Caltech, JPL
74 Jorgensen, 12:00 pm

Asking the Right Questions and Understanding the Answers in Software Testing
When hunting for buried treasure, it is essential to both walk over the right spot on the beach and to carry a working metal detector. When hunting for the subtle software defects that can plague (and crash) space missions, it is important to run the right tests and to actually detect incorrect behaviors that appear during those tests. We present a brief tutorial component, describing some of the challenges of choosing tests and monitoring tests for symptoms of faults. We also present ongoing research in responding to these challenges in the context of JPL flight software, including the in-development file systems for the Mars Science Laboratory mission (JPL's next Mars rover, launching in 2009).

Tuesday, February 12, 2008
Erik Winfree, Caltech
74 Jorgensen, 12:00 pm

Learning to Program Chemistry
Biological organisms are extremely sophisticated self-organized chemical systems. Their complexity dwarfs anything produced by modern chemical industries. The difference can be ascribed in large part to biological systems being information-processing machines: DNA, RNA, and proteins carry molecularly-encoded messages that direct all of life's processes. Biology is programmable chemistry. Can we learn how to program chemistry? How will this expand the capabilities of synthetic chemistry? Might non-biological chemistries also be programmable? What kinds of models of computation are needed for understanding how to program chemistry and the limits to doing so? I cannot give conclusive answers to these questions, but I will present examples of what we have learned while creating self-assembling structures, molecular machines, and logic circuits built out of DNA, RNA, and the occasional enzyme. I will argue that the key to unleashing the revolutionary potential of programmable molecular systems lies in understanding the design space and managing their complexity as information processing systems -- issues that are fundamental to computer science.

Tuesday, February 5, 2008
Paul Upchurch, Caltech Computer Science & JPL
74 Jorgensen, 12:00 pm

Visualization of Large Scale Environments
The number of people playing online games continues to increase each year. Game engine technology is generating innovations in hardware and software. This project investigates the use of game engines at JPL for interactive visualizations of explorations of the solar system.

This talk describes GoView a scriptable game engine which is tailored for rendering spacecraft trajectories in the solar system. Rendering trajectories across the solar system poses challenges that are not encountered in popular online games such as Doom. In particular, the game engine must be able to handle spatial scenes larger than six orders of magnitude. The talk describes the problems encountered and how they are solved in GoView.

Interactive visualizations of explorations of the solar system are being developed at JPL for public outreach, mission planning and mission operations.

Tuesday, January 29, 2008
Joel W. Burdick, Caltech
74 Jorgensen, 12:00 pm

Engineering Interfaces to Damaged Nervous Systems
This talk will introduce some of the challenges involved in trying to develop technology that can partially restore some functionality to people with severe neural deficiencies. The first part of the talk (which is based on joint work with Prof. Richard Andersen and Prof. Y.C. Tai of Caltech) will focus on neural prostheses. A neuroprosthetic is a brain-machine interface that can potentially enable a paralyzed human, via the use of surgically implanted electrode arrays, and associated computer decoding algorithms, to control external electromechanical devices. The problem of decoding the prosthetic user's intent from the recorded neural sisgnals is a problem in inference, or estimation. A few of the estimation techniques that have been used to solve this problem will be reviewed. Progress on making adaptive electrodes that autonomously optimize the quality of the brain-machine interface will also be reviewed.

The second half of the talk (which is based on joint work with Prof. Reggie Edgerton of UCLA and Prof. Y.C. Tai of Caltech) will focus on the problems involved in partially restoring locomotion after a severe spinal cord injury. While there are an enormous number complex issues surrounding a spinal injury, this talk will focus on the use of drug therapy, automated machines for physical therapy, and a new class of epidural spinal cord stimulators to help with the locomotion rehabilitation process. Each of these therapeutic components also have associated computational and algorithmic problems. For example, we are currently trying (in collaboration with Prof. Yaser Abu-Mostafa of Caltech) to formulate the problem of selecting the correct electrode stimulation protocols as a problem in kernel learning.

Tuesday, January 22, 2008
Jason Marden and Adam Wierman
74 Jorgensen, 12:00 pm

A Game Theoretic Formulation of the Sensor Allocation Problem
Interdisciplinary research at the junction of information sciences, economics and game theory offers new solutions to several problems. This talk looks at applying game theory to solve a problem in cooperative control in distributed systems: the optimal locations of sensors in a sensor network.

This talk is introductory. The problem domain and basic concepts will be described. Detailed proofs will be given in other seminars and are also found in papers.

This talk presents a view of cooperative control using the language of learning in games. Specifically, we look at the cooperative control problem of dynamic sensor allocation. We formulate the sensor allocation problem as a noncooperative game where the decision makers are the sensors. In this setting, each sensor is assigned a local objective or utility function and is given the ability to autonomously alter it's position and sensing activity in real time. The distributed nature of the decision making allows for robustness to communication failures, sensor failures, and environmental changes. In this talk we will discuss several methods for designing the sensors' local utility functions. We measure the efficacy of a particular utility design in two ways: (i) Does a Nash equilibrium exist? (ii) How efficient is a Nash equilibrium when compared to the optimal allocation?