Colloquium

MyLifeBits is a lifetime store of everything. It is the fulfillment of Vannevar Bush's 1945 Memex vision including full-text search, text & audio annotations, and hyperlinks. MyLifeBits is both an experiment in lifetime storage and a software research effort. In this talk, we will demonstrate the software we have developed for MyLifeBits, which leverages SQL server to support: hyperlinks, annotations, reports, saved queries, pivoting, clustering, and fast search. MyLifeBits is designed to make annotation easy, including gang annotation on right click, voice annotation, and web browser integration. It includes tools to record web pages, IM transcripts, radio and television. The MyLifeBits screensaver supports annotation and rating. We are beginning to explore features such as document similarity ranking and faceted classification. We have collaborated with the WWMX team to get a mapped UI, and with the SenseCam team to digest and display SenseCam output. www.mylifebits.com has more information. One of the demos will be based on the summer intern project of Aleks Aris from UMd.

The C++ programming language is now 25 years old, and used by millions of programmers. Developing such a language is a challenging business. I will present a personal view of some of the factors that were and still are critical for C++'s sustained success. Many of the ideals and principles that were applied -- with varying degrees of success -- involve non-technical concerns. Real-world language evolution differs significantly from "green field" and "blue sky" design, since it requires long-term evolution in a world of shifting external pressures rather than specifying an ideal design once and for all.

Combinatorial auctions (CAs) allow one seller to allocate a collection of heterogeneous and discrete goods to multiple buyers, each of which may have complex valuations, e.g. "I only want A if I get B" , "I only want A or B", etc. Yet, many real world problems (such as resource allocation on Federated systems like PlanetLab) are more naturally two-sided, with multiple buyers and sellers. Combinatorial Exchanges (CEs) extend CAs to this two-sided setting. In this talk, I outline three key components in our exchange design: a tree-based bidding language, adaptive preference elicitation, and a payment rule to promote simple and truthful bidding. In moving towards a deployment of such a market for computational resources, I discuss some of the wider, institutional and technological, issues that must be addressed. In closing, I mention some additional directions in computational mechanism design that will impact resource allocation and arbitration in real systems.

A clear understanding of how the brain works will make it possible for us to build intelligent machines, in silicon, that will exceed our human ability in surprising ways. The brain is not a computer, but a memory system that stores experiences in a way that reflects the true structure of the world, remembering sequences of events and their nested relationships and making predictions based on those memories. It is this memory-prediction system that forms the basis of intelligence, perception, creativity, and even consciousness. The neocortex is the seat of most aspects of perception and high-level thought. I propose that the neocortex can be understood as a hierarchical sequence memory. This talk will describe the anatomy and physiology of the cortex, and show that they can be accurately captured by a mathematical model based on conditional probabilities. An implementation of this system will be shown that demonstrates robust invariant image recognition.

ABSTRACT: Many NP-complete problems are easy for random inputs. For example, in a random graph where each edge is present with probability 1/2 one can find a Hamiltonian cycle in linear time, almost surely. On the other hand, random instances of satisfiability and graph coloring appear to be hard. Moreover, each problem appears to be hardest near its "threshold", a constraint density around which the probability of solubility drops rapidly from near 1 to near 0. Locating these two thresholds and understanding the behavior of algorithms near them is an active topic of research in artificial intelligence, combinatorics, probability, theoretical computer science, and statistical physics.

We study how the structure of the set of solutions evolves in each of these two problems as constraints are added. This allows us to determine the location of the threshold for both random satisfiability and random graph colorability up to second order terms. To do this we prove that for a large class of random constraint satisfaction problems the second moment of the number of solutions is captured by an "entropy-energy" tradeoff. Critical values of this tradeoff correspond to points where the structure of the space of solutions undergoes dramatic change. By identifying these critical points, we not only get to locate thresholds but we also gain rigorous insight on why algorithms have a hard time near them.

Based on joint works with Assaf Naor (Microsoft) and Yuval Peres (Berkeley).

We study the problem of designing seller optimal auctions. Prior to this work, the only previously known auctions that are approximately optimal in worst case employ randomization. Our main result is the existence of deterministic auctions that approximately match the performance guarantees of these randomized auction. We give a fairly general derandomization technique for turning a randomized mechanism into an asymmetric deterministic one with approximately the same properties. In doing so, we bypass an impossibility result for symmetric deterministric aucyions by using asymmetry, i.e., the order in which bids appear in the input.

Our derandominazion technique uses an auxillary graph of exponential size and takes exponential time even if the corresponding randomized auction is polynomial time. We leave as an open question the existence of a polynomial-time computable deterministic auction that is approximately optimal.

Our work shows an interesting relationship between mechanism design and several areas of computer science, including competitive algorithms, computational learning, and coding theory.

Joint work with Gagan Aggarwal, Amos Fiat, Nicole Immorica, Jason Jason Hartline, and Madu Sudan.

Human perceptual skills are remarkable, but largely underutilized by current graphical user interfaces. The next generation of animated GUIs and visual data mining tools can provide users with remarkable capabilities if designers follow the Visual Information-Seeking Mantra: Overview first, zoom and filter, then details-on-demand Then dynamic queries allow user control of widgets, such as sliders and buttons that update the result set within 100msec. Seven types of information visualizations (1-, 2-, 3-, multi-dimensional data, temporal, tree and network data) will be shown in examples for U.S. Census, time series searching, and gene expression data. Commercial success stories based on our early work include multi-dimensional data in dynamic scattergrams (www.spotfire.com), hierarchical stock market data in treemaps (www.smartmoney.com/marketmap), and production monitoring/product catalogs in treemaps (www.hivegroup.com).

This talk will emphasize scientific and statistical data analysis such as gene expression studies, multi-variate temporal data sets, and hierarchical clustering. For more info and to download programs, visit: www.cs.umd.edu/hcil/treemap www.cs.umd.edu/hcil/timesearcher www.cs.umd.edu/hcil/hce

Leonardo's Laptop: Human Needs and the New Computing Technologies http://mitpress.mit.edu/leonardoslaptop

Winner of IEEE book award for "Distinguished Literary Contribution furthering Public Understanding of the Profession"

Ben Shneiderman (ben@cs.umd.edu) Department of Computer Science, Human-Computer Interaction Laboratory, Institute for Advanced Computer Studies & Institute for Systems Research University of Maryland, College Park, MD 20742

The old computing was about what computers could do; the new computing is about what people can do.

To accelerate the shift from the old to the new computing designers need to: 1) reduce computer user frustration. Recent studies show 46% of time is lost to crashes, confusing instructions, navigation problems, etc. Public pressure for change could promote design improvements and increase reliability, thereby dramatically enhancing user experiences.

2) promote universal usability. Interfaces must be tailorable to a wide range of hardware, software, and networks, and users. When broad services such as voting, healthcare, and education are envisioned, the challenge to designers is substantial.

3) envision a future in which human needs more directly shape technology evolution. Four circles of human relationships and four human activities map out the human needs for mobility, ubiquity, creativity, and community. The World Wide Med and million-person communities will be accessible through desktop, palmtop and fingertip devices to support e-learning, e-business, e-healthcare, and e-government.

Leonardo da Vinci could help as an inspirational muse for the new computing. His example could push designers to improve quality through scientific study and more elegant visual design. Leonardo's example can guide us to the new computing, which emphasizes empowerment, creativity, and collaboration. Information visualization and personal photo interfaces will be shown: PhotoMesa (www.cs.umd.edu/hcil/photomesa) and PhotoFinder (www.cs.umd.edu/hcil/photolib).

For more: http://mitpress.mit.edu/leonardoslaptop http://www.cs.umd.edu/hcil/newcomputing

Ben Shneiderman is a Professor in the Department of Computer Science Founding Director (1983-2000)of the Human-Computer Interaction Laboratory (http://www.cs.umd.edu/hcil/), and Member of the Institutes for Advanced Computer Studies & for BEN SHNEIDERMAN is a Professor in the Department of Computer Science Founding Director dies & for Systems Research, all at the University of Maryland at College Park. He was elected as a Fellow of the Association for Computing (ACM ) in 1997 and a Fellow of the American Association for the Advancement of Science (AAAS) in 2001. He received the ACM SIGCHI Lifetime Achievement Award in 2001.

Ben is the author of "Software Psychology: Human Factors in Computer and Information Systems" (1980) and "Designing the User Interface: Strategies for Effective Human-Computer Interaction" (4th ed. 2004) http://www.awl.com/DTUI/ . He pioneered the highlighted textual link in 1983, and it became part of Hyperties, a precursor to the web. His move into information visualization helped spawn the successful company Spotfire http://www.spotfire.com/ . With S Card and J. Mackinlay, he co-authored "Readings in Information Visualization: Using Vision to Think" (1999). "Leonardo's Laptop" (MIT Press) appeared in October 2002, and his new book with B. Bederson, "The Craft of Information Visualization" was published in April 2003.

We outline the paper and pencil correctness proof for an operating system microkernel written in C. The key ingredients of the proof are 1) a simulation of virtual machines by physical processors with swap memory. Here physical memory serves as a cache for virtual memory. In the correctness proof one argues simultaneously about hardware (memory management units) and low level software (page fault handlers). 2) semantics and provably correct compiler for an appropriate subset of C. One needs small steps semantics resp. structured operational semantics, because the computations of the kernel needs to be interleaved with computations of the users. One needs also to consider in line assembler code, because the variables of an abstract C machine do not show the user processes. The correctness proof for the compiler is nontrivial, because the recursion of small steps semantics does not match the recursion for the code generation very well. 3) the definition of an abstract machine model for an operating system kernel providing multiprocessing and virtual memory. In this model interrupt handling and function calls can be treated in a very uniform way. The simulation of this model by a physical machine combines the techniques from the first two parts. This is joint work with M. Gargano, M. Hillebrand and D. Leinenbach. It is part of a large project funded by the German national government, which aims at the formal verification of entire computersystems consisting of hardware, system software, communication system and applications.