2009 | 2008

Tuesday, December 1, 2009
Alain Martin, Professor of Computer Science
105 Annenberg, 12:00 pm

We all know that the microprocessors in our computers use a clock. The clock enforces sequencing in a VLSI implementation of a digital computation. The clocking protocol relies on a knowledge of gate and wire delays that constitutes both an advantage and a drawback. Its advantage is simplicity. But as increasing parameter variability makes this knowledge less and less precise, the drawbacks are starting to outweigh the advantages.

In this talk, I will present an overview of asynchronous logic, a design approach for digital VLSI that does not use clock. I will show that delay insensitivity---i.e. the complete ignorance of delays---is impossible. Instead, I will introduce the concept of "quasi-delay-insensitivity'' (QDI), in which a minimal timing assumption, the "isochronic fork'' is sufficient for implementing any computation. I will briefly describe the several asynchronous microprocessors designed at Caltech, their robustness and efficiency in the presence of large parameter variations, and their energy efficiency. Finally I will argue that the use of asynchronous logic may be unavoidable for emerging technologies like nano (CNT and SNW) and organic electronic.

Tuesday, November 17, 2009
Babak Hassibi, Professor of Electrical Engineering, Caltech
105 Annenberg, 12:00 pm
Information Flow in Networks

Tuesday, November 10, 2009
Fletcher Wicker, The Aerospace Corporation
105 Annenberg, 12:00 pm

Wireless Spectral Sharing Techniques and Issues
The demand for satellite communications has grown dramatically over the past decade. Currently there is very little unused radio frequency spectrum available for use in satellite communications. New satellite-based applications such as high-definition TV and high-speed Internet access require more bandwidth than is available. This presentation investigates how direct-sequence spread-spectrum techniques can be used to share spectral bands that are currently allocated to ground-based narrowband users. The use of spread-spectrum techniques theoretically should allow satellite communications to co-exist with narrowband users. However, additional measures to ensure that the operations are on a non-interference basis are required. An analysis of the traffic generated by narrowband users is presented along with some unusual spectral phenomena.

Tuesday, November 3, 2009
Leeat Yariv, Associate Professor of Economics, Caltech
105 Annenberg, 12:00 pm

Matching Markets in the Lab
Matching markets have an important role in the economy. They determine such varied outcomes as which student goes to what school, who gets which job, who marries whom, and who buys which house. In fact, recent theoretical work on matching has been useful for the design of markets as well as for the repair of market failures. There are two main questions that are at the heart of the matching literature. First, from a policy perspective, how do different institutions (centralized and decentralized) fare in terms of outcomes? Second, from a positive perspective, when observing outcomes in matching markets, what can we deduce about participants’ preferences (individuals’ preferences over mate characteristics, parents’ preferences over child attributes, etc.)? This talk will provide an introduction to the theory of matching and an overview of some recent lab experiments conducted at Caltech designed to identify the important market features that impact ultimate matching outcomes.

Tuesday, October 27, 2009
John Ledyard, Allen and Lenabelle Davis Professor of Economics and Social Sciences
105 Annenberg, 12:00 pm

Computational Mechanism Design
Mechanism design is a subfield of economics that is rather unique within economics in having an engineering perspective. It is interested in designing mechanisms, just like computer scientists are interested in designing algorithms, protocols, or systems." (Noam Nisan in Algorithmic Game Theory) Economists, however, have tended to ignore computation and communication constraints in their theoretical work. Algorithmic Game Theory and Computational Mechanism Design rectify this. Computational Mechanism Design is both a theoretical and an applied enterprise. Among other things, it studies auction and market design. It draws on models and principles from game theory, economics, computer science, and operations research. In my talk, I will introduce some of the basic concepts, point to some of the interesting theoretical results, and discuss some of the practical difficulties and open questions by considering the methodology of market design.

Tuesday, October 20, 2009
Charles Plott, Edward S. Harkness Professor of Economics and Political Science, Caltech
105 Annenberg, 12:00 pm

A Combinatorial Double Auction Exchange to Solve a Complex Environmental Problem: The Native Vegetation Exchange
In Victoria, Australia individuals or firms wishing to proceed with economic developments (subdivisions, shopping centers, roads) that involve the clearing of native vegetation are required to obtain an offset to replace the vegetation destroyed. This offset must be in the form of an area of "environmentally equivalent" vegetation that the owner/farmer agrees to maintain and preserve for a contracted " long period" of time. The contracts between developer and farmer must be negotiated in the presence of substantial non-convexities on both the buyer and seller sides of any transaction, leading to the economic need to find groups of buyers and sellers to be included in many transactions. In addition, the problem involves asymmetric and local information and all transactions must meet governmentally specified concepts of "equivalent vegetation". This paper focuses on the design and testing of a "smart market" that operates through optimization constrained by the offset trading rules, combinatorial bidding preferences (or package bidding) on both the buyers' and the sellers' side, and strategic tools (including search and query functions and 'market making'), to encourage competitive trading activity. The electronic exchange is scheduled to be introduced as the Native Vegetation Exchange. A series of experimental tests were used to evaluate the ability of the exchange to perform in the expected environment at appropriate scale, the software performance, usability and to elucidate specific bidding behaviour and to assess efficiency.

Tuesday, October 13, 2009
Joel Tropp, Assistant Professor of Applied and Computational Mathematics
105 Annenberg, 12:00 pm

Finding Structure with Randomness: Stochastic Algorithms for Computing Approximate Matrix Decompositions
Computer scientists have long known that randomness can be used to improve the performance of algorithms. A familiar application is the process of dimension reduction, in which a random map transports data from a high-dimensional space to a lower-dimensional space while approximately preserving some geometric properties. By operating with the compact representation of the data, it is theoretically possible to produce approximate solutions to certain large problems very efficiently. Recently, it has been observed that dimension reduction has powerful applications in numerical linear algebra and numerical analysis. This talk provides a high-level introduction to randomized methods for computing standard matrix approximations, and it summarizes a new analysis that offers (nearly) optimal bounds on the performance of these methods. In practice, the techniques are so effective that they compete with---or even outperform---classical algorithms. Since matrix approximations play a ubiquitous role in areas ranging from information processing to scientific computing, it seems certain that randomized algorithms will eventually supplant the standard methods in some application domains.

Tuesday, June 2, 2009
Yuri Lifshits, Yahoo! Research
74 Jorgensen, 12:00 pm

Data Cloud: Integrating Structured Information into Web Search
In this talk we address two questions:

1) How to use structured data in web search?
2) How to gather structured data?

For the first question we identify valuable classes of data, present query classes that can benefit from structured data and describe architecture that combines keyword search with structured search.

For the second question we present Data Cloud: An ecosystem of data publishers, search engine (data cloud) and data consumers. We show connection form Data Cloud Strategy to classic notion in economics: network effect in two-sided markets.

At the end of the talk an early demo implementation will be presented.

Tuesday, May 26, 2009
Mathieu Desbrun, Computer Science, Caltech
74 Jorgensen, 12:00 pm

Making a Mesh
Meshing lies at the heart of many computational techniques across a wide range of fields. This task consists of finding a set of simple elements (typically vertices, edges, triangles, tetrahedra) which best partition a given domain while approximating its boundaries. However, meshing a domain is complicated by requirements on the "quality" of the mesh: badly shaped elements (too flat, stretched, etc.) must be avoided as the presence of even a single one can ruin the convergence and/or accuracy of a computational method. In this talk, we will provide an introduction to meshing, focusing on the simple yet common case of isotropic tetrahedral meshing. Links to Delaunay/Voronoi tessellations, approximation theory, and basic high-school geometry will be pointed out to help design good meshes easily---and we'll also briefly mention what to do with them once you have them.

Tuesday, May 19, 2009
Tracey Ho, Assistant Professor of Electrical Engineering and Computer Science, Caltech
74 Jorgensen, 12:00 pm

Tuesday, May 12, 2009
Richard Murray, Engineering and Applied Science, Caltech
74 Jorgensen, 12:00 pm

Feedback and Control in Biological Circuit Design
Biological systems make use of feedback in an extraordinary number of ways, on scales ranging from molecules to cells to organisms to ecosystems. In this talk I will discuss the use of concepts from control and dynamical systems in the analysis and design of biological feedback circuits at the molecular level. After a brief survey of advances in synthetic biology, I will present some recent results that combine modeling, identification, design and experimental implementation of biological feedback circuits. Using these results as examples, I will discuss some of the open problems and research challenges in the area feedback control using biological circuits.

Tuesday, May 5, 2009
Chris Umans, Associate Professor of Computer Science, Caltech
74 Jorgensen, 12:00 pm

Local Decoding of Polynomials and its Applications
Error-correcting codes lie at the heart of a number of powerful results in Computer Science. Among the most useful error-correcting codes are codes based on polynomials, and they derive their error-correcting properties from the fact that polynomials of low degree cannot have many roots.

Certain polynomial-based codes have an amazing additional property: any given symbol of the original encoded information string can be retrieved from a corrupted codeword by examining only a tiny fraction of the overall object. This is called "local decoding." The existence of locally decodable codes is crucial to a number of the most striking uses of algebra in theoretical computer science. I'll describe some of these applications: I'll sketch how locally decodable codes are used in Probabilistically Checkable Proofs (mathematical proofs whose validity can be checked by randomly examining only a tiny portion of the proof), and how locally decodable codes are used in the transformation of computationally hard problems into "even harder" problems (which are in turn useful in cryptography and elsewhere within Computational Complexity).

Tuesday, April 28, 2009
Federico Echenique, Associate Professor of Economics, Caltech
74 Jorgensen, 12:00 pm

Aggregation: When Many Behave as One
When does a group of independent and egoistic agents behave as one "representative" agent? What are the properties of such aggregate behavior? I shall survey some standard results on aggregation in economics, and present some new results developed with my colleague Chris Chambers. We study a collective that is less averse to risk then its individual members. We study the ways on which such a collective can aggregate its behavior.

Tuesday, April 21, 2009
Roy Williams, Center for Advanced Computing Research, Caltech
74 Jorgensen, 12:00 pm

Real-Time Astronomy with Skyalert
There is a waterfall coming of astronomical surveys that discover change in the sky, and the data rates are of course exponentiating. Such transient events may be supernovae, gamma-ray bursts, cataclysmic variables, blazar eruptions, etc. To understand the astrophysics of these rapid followup observation is needed, and as rates increase, decisions will of necessity be made by automated systems. I will present a prototype of such a system.

Tuesday, April 14, 2009
Michelle Effros, Professor of Electrical Engineering, Caltech
74 Jorgensen, 12:00 pm

A Brief Look at Data Compression
Data compression is pervasive in today's computer and communication technology. You use it to store images on your digital camera, save music on your mp3 player, share videos over the web, watch movies on DVDs, and even make phone calls. When done well, the presence of data compression in your life is almost imperceptible. But how does data compression work? And given that data compression is already almost everywhere, what could possibly be left to be done? I will introduce a few key concepts that explain why data compression is possible and where the unmined potential for future improvements lies.

Tuesday, April 7, 2009
Yaser S. Abu-Mostafa, Learning Systems Group, Caltech
74 Jorgensen, 12:00 pm

Learning from Data
If you show a picture to a three-year-old and ask him if there is a tree in it, he is likely to give you the right answer. If you ask a thirty-year-old what the definition of a tree is, he is likely to give you an inconclusive answer. We didn't learn what a tree is by studying the mathematical definition of trees. We learned it by looking at a lot of trees. In other words, we learned from data. Learning from data is used in situations where we don't have an analytic solution, but we have data that we can use to construct an empirical solution. It is one of the most widely utilized techniques in science, engineering, medicine, and economics. In this talk, I will introduce the main concepts and techniques of learning from data. I will also give examples of the practical applications of this field.

Tuesday, March 31, 2009
Gerard Holzmann, JPL/NASA Laboratory for Reliable Software
74 Jorgensen, 12:00 pm

Catching Bugs
We have gotten used to the fact that almost all our daily activities are now enabled by, or affected by, the use of computers. The truth is that we live in an extraordinary period of time where the amount of software that supports our infrastructure is increasing exponentially fast. This does not just apply to our laptops or desktop PCs, but also to the software that helps to control the airplanes we fly and the cars we drive.

When the size and complexity of even safety critical software application is changing this fast, it becomes especially important that we pay close attention to the processes that are followed to develop that software, and the methods we use to get it right. In this talk, I will describe how at JPL we are starting to infuse new theoretical insights in software design, testing and formal verification into the software development life cycle, to help address some of these issues.

Tuesday, March 3, 2009
Maren Boese, Seismo Lab, GPS, Caltech
74 Jorgensen, 12:00 pm

Information Technology and Earthquake Early Warning Systems
Earthquake Early Warning (EEW) requires fast and robust predictions of earthquake source (magnitude, location,...) and ground motion parameters (peak ground acceleration/displacement,...) shortly after the occurrence of a moderate to large earthquake. If given in a timely manner, warnings can be used at distant sites to trigger and execute automatic measures to prevent or reduce the damage that could be caused by the later arriving high-amplitude seismic waves. The two major challenges in EEW, maximum reliability at maximum warning time, can be archived by expanding, up-grading, and optimizing of seismic sensor networks, such as of the California Integrated Seismic Network (CISN). The CISN uses around 450 broadband and strong motion sensors deployed at around 300 locations across California. The real-time transmission of waveform data to the central processing facilities at UC Berkeley, the U.S. Geological Survey (USGS) Menlo Park, and Caltech includes satellite communications (radio, frame relay, and cell phone services) and publicly available internet services (DSL). Within a feasibility study funded by the USGS, we currently test different approaches for EEW using the infrastructure of the CISN. These include the so-called on-site warning approach that has been implemented at Caltech and that has been real-time tested during several small to moderate-sized earthquakes in the past two years.

Large magnitude earthquakes (M>>7.0) with ruptures of up to hundreds of kilometers length cause damaging ground motions in much larger areas than moderate and strong earthquakes. Despite of their rare occurrence, much more people and users could benefit from an EEW system during large events. A large earthquake on the southern San Andreas Fault is overdue. As recently demonstrated ("The Great Southern California ShakeOut"; Jones et al., 2008), warning times for Los Angeles could be in the order of 70-80 seconds. As the fault rupture of large earthquakes can take up to several minutes, magnitude predictions need to be up-dated automatically with time as the rupture is growing. We have developed a probabilistic method to EEW based on the Bayesian approach to quantify the uncertainties of each of these predictions.

Tuesday, February 24, 2009
Dan Meiron, Fletcher Jones Professor of Applied & Computational Mathematics and Computer Science
74 Jorgensen, 12:00 pm

Large Scale Data Analysis Challenges
JASON, a scientific advisory group, was asked by representatives of the Department of Defense (DOD) and the Intelligence Community (IC) to recommend ways in which the DOD/IC can handle present and future sensor data in fundamentally different ways, taking into account both the state-of-the-art, the potential for advances in areas such as data structures, the shaping of sensor data for exploitation, as well as methodologies for data discovery.

In this presentation we will examine the challenges associated with the analysis of large data and in particular compare DOD/IC requirements to those of several data intensive fields such as high energy physics and astronomy. The conclusion is that while DOD/IC data requirements are certainly significant, they are not unmanageable given the capabilities of current and projected storage technology.

The key challenge will be to adequately empower DOD and IC analysts by matching analysis needs to data delivery modalities. At a very cursory level, we will examine some current approaches that could enable better information fusion. We'll also propose various grand challenges that could be used to assess and prioritize future research efforts in data assimilation and fusion.

Tuesday, February 17, 2009
Rajit Manohar, Cornell University
74 Jorgensen, 12:00 pm

VLSI Systems: Past, Present, and Future Trends
I examine some of the trends in VLSI design, and how increases in transistor count have led to improvements in performance. Scaling predicts that we might be able to design chips that have almost 50B devices on them. What can we do with all these devices given the challenges facing modern designers? This talk examines a number of different answers to this question that are currently being proposed, and argues why asynchronous design is an important part of the solution.

Tuesday, February 10, 2009
Andreas Krause, Caltech
74 Jorgensen, 12:00 pm

Thoughts About Sensing
Sensors are everywhere: Examples include community-owned sensors such as cameras and accelerometers in cell phones, GPS receivers and navigation devices in cars, infrastructural sensors such as smart meters in the power grid, sensors for environmental monitoring and many others. Harnessing these sensing resources could have enormous benefit on the productivity, quality and security of our society.

In order to make use of these resources, we need to address important research challenges: How can we model and robustly reason about data obtained from heterogeneous, noisy sensors? How can we efficiently make informed, distributed decisions under uncertainty? How can we cope with constraints dictated by limited battery, computational power, communication capability as well as by preferences about privacy? How can we extract most useful information from the massive amounts of data originating from large-scale sensor and information networks?

I will discuss some of these challenges and possible approaches to address them in the context of real-world sensing problems, including autonomous environmental monitoring, traffic prediction and detecting contamination in drinking water distribution networks.

Tuesday, February 3, 2009
Jehoshua (Shuki) Bruck, Caltech
74 Jorgensen, 12:00 pm

Random Ideas About Biology
Why does the functioning of biological systems seem miraculous? One reason is that we do not know how to design systems that do what cells do, namely molecular computing. In contrast, we know how to design highly complex information systems. The fundamental reason for the successful evolution of information systems is the development of mathematical abstractions that enable efficient and robust design processes. In particular, Claude Shannon in his classical 1938 Master Thesis demonstrated that all Boolean functions can be computed by relay circuits, leading to the development of digital logic and resulting in computer chips with over a billion transistors. Motivated by the challenge of analyzing stochastic gene regulatory networks, we generalize the notion of logic design to probabilistic logic design. Specifically, we consider relay circuits where deterministic switches are replaced by probabilistic switches. We present efficient algorithms for synthesizing probabilistic relay circuits that can compute probability distributions.

Tuesday, January 27, 2009
Robert (Bob) Graham, Southern California Edison
74 Jorgensen, 12:00 pm

Electricity...Sustaining our Transportation Future
President-elect Obama has discussed plug-in hybrid vehicles (PHEV) as a significant component of his energy security plan. US auto makers - Ford, GM, and Chrysler have all announced PHEV and battery electric vehicle (BEV) production programs with expected deliveries beginning in late 2010 and expanding throughout 2011. The State of California published a carbon reduction goal for 2050, which includes electric fuel as one of the critical path options necessary to achieve this important objective. Market penetration for PHEV vehicles can be as high as 60% by 2030, meaning a production level (based on the last few years) nearing 7 million vehicles per year. What needs to be accomplished to ready the electricity infrastructure to support a transition from fossil fuel to electricity? What technologies need to mature to build reliability and confidence? What new technologies need to be developed to drive the cost down and the efficiency up? What Information Science and Technology developments will be required to support continuous global growth? Bob Graham will discuss these issues and Southern California Edison's vision for the future in sustainable alternative-fuel technologies.

*You will get to see a new electric car in the parking lot behind Jorgenson after the talk.*

Tuesday, January 20, 2009
Alexei Kitaev, Caltech
74 Jorgensen, 12:00 pm

Topological Quantum Computation
To achieve scalability, a quantum computer must tolerate some amount of de-coherence and inaccuracy in the gate implementation. This issue may be addressed by using quantum error-correcting codes, but that only works if the physical gates are sufficiently good. In may talk, I will discuss an alternative approach in which the errors are eliminated at the physical level. The role of the error-correcting code is played by a degenerate ground state of a suitable quantum system cooled to a low temperature. In this scheme, the protection against errors is due to topology.

Tuesday, January 13, 2009
Changhuei Yang, Caltech
74 Jorgensen, 12:00 pm

Is Your Cell Phone Ready to be Your Doctor?
Cell phones and their ubiquitous presence in our lives suggest that the technology may be a key enabler of telemedicine. The incorporation of medical functionalities into a cell phone can have significant impacts in improving healthcare broadly for low-resource communities, as well as highly networked urban cities. This talk will examine and explore some of the possible add-on components that can turn a cell phone into a medical tricorder.