Past Lunch Bunches

2008 | 2007 | 2006 | 2005

March 21, 2006
Herbert Edelsbrunner, Duke University

Noise and Topology
How to separate noise from signal is a fundamental problem anywhere we deal with sensed data. We take the view that this difference is in the eye of the beholder. To cope with the problem, we suggest to assess all features numerically and to separate noise from signal using a threshold that may vary possibly even locally.

We demonstrate that algebraic topology offers tools that can be used to implement this idea for continuous functions. Specifically, we use homology groups of sublevel sets to represent a functions combinatorially, as a discrete set of points in the plane. We show that this diagram is a stable representation and mention a few consequences of this structural result.

Lunch Will Be Served.

April 18, 2006
Nachiket Kapre, Caltech

Packet-Switched vs. Time-Multiplexed FPGA Overlay Networks
Dedicated, spatially configured FPGA interconnect is efficient for applications that require high throughput connections between processing elements (PEs) but with a limited degree of PE interconnectivity (e.g. wiring up gates and datapaths). Applications which virtualize PEs may require a large number of distinct PE-to-PE connections (e.g. using one PE to simulate 100s of operators, each requiring input data from thousands of other operators), but with each connection having low throughput compared with the PE's operating cycle time. In these highly interconnected conditions, dedicating spatial interconnect resources for all possible connections is costly and inefficient. Alternatively, we can time share physical network resources by virtualizing interconnect links, either by statically scheduling the sharing of resources prior to runtime or by dynamically negotiating resources at runtime.

We explore the tradeoffs (e.g. area, route latency, route quality) between time-multiplexed and packetswitched networks overlayed on top of commodity FPGAs. We demonstrate modular and scalable networks which operate on a Xilinx XC2V6000-4 at 166MHz. For our applications, timemultiplexed, offline scheduling offers up to a 63% performance increase over online, packet-switched scheduling for equivalent topologies. When applying designs to equivalent area, packetswitching is up to 2◊ faster for small area designs while timemultiplexing is up to 5◊ faster for larger area designs. When limited to the capacity of a XC2V6000, if all communication is known, time-multiplexed routing outperforms packet-switching; however when the active set of links drops below 40% of the potential links, packet-switched routing can outperform timemultiplexing.

October 17, 2006
Sven Koenig, University of Southern California

Market Mechanisms for Agent Coordination
In this talk, I will give an overview of our research on market mechanisms for the allocation of resources in cooperative domains. As example, I will use exploration tasks where a team of mobile robots needs to visit a number of given targets in known or partially unknown terrain. An important characteristic of these multi-robot routing tasks is that the assignment of targets to robots can turn out to be suboptimal as the robots gain more information about the terrain. Auctions promise to assign and re-assign targets to robots efficiently in terms of both the required amount of computation and communication since information is compressed into numeric bids that the robots can compute in parallel. I will discuss the advantages and disadvantages of different auction mechanisms, including recent theoretical results that show that sequential single-item auctions can provide constant factor performance guarantees in known terrain even though they run in polynomial time. This is joint work with D. Kempe, P. Keskinocak, M. Lagoudakis, V. Markakis, A. Meyerson, C. Tovey and our students.

October 31, 2006
Mathieu Desbrun

November 7, 2006
Michael Langberg

Classification of Incomplete Data
One of the great challenges in computational theory is the extraction of patterns from massive and high-dimensional data sets, e.g., clustering. The usual starting point is an input set consisting of a list of empirically gathered data points in R^d. One of the serious gaps between statistical theory and practice, however, lies with incompletely-specified data. Essentially, the issue is that a high-dimensional data point is not specified by one "measurement" but by many, and that some of those measurements may be missing. From a geometric viewpoint, a data item for which some measurements are missing is simply an affine subspace. In some cases it must be an axis-parallel subspace (e.g., data obtained from sliding-bar surveys) but in others (data gathered by sensors) it is not.

In this talk, I Michael will present some recent results on the clustering of incomplete data. Our results are based on two (new) theorems in combinatorial geometry, both of which can be viewed as an extension to the well known Helly theorem.

November 28, 2006
Jason Hickey

Mechanized Reflection
Very generally, reflection is the ability of a logical system to be "self-aware" in some way. It is the key tool that Godel used to prove his incompleteness theorem in 1931. It has practical application including super-exponential reduction in the size of some proofs, in logics of knowledge "I know that he knows that I know that ...", and it is especially useful in proving meta-properties of logics. Standard techniques, such as Godel-numbering of formulas, are hopeless for mechanized reasoning--the history of reflection is filled with failed efforts. In this talk, I will show that reflection can be mechanized when the structure of formulas is preserved (much like Lisp macros preserve the structure of Lisp programs), and that reflection is the mechanism of choice when reasoning about programming languages.

| top |