Department
Computer Science Department
Institution
Carnegie Mellon University
Education
Not mentioned yet.
Research Interests
Biography
I have worked in a variety of different areas of computer science, including amortized analysis of algorithms, self-adjusting data structures, competitive algorithms, natural language parsing, computer game playing, synthesis of musical sounds, and persistent data structures.
Natural Language: I (jointly with co-author Davy Temperley) wrote a parser for English. The system (which we call a link grammar) is unlike phrase structure parsing or context free parsing. The scheme is elegant and simple, and our grammar captures a very wide variety of complex phenomena in English. We (John Lafferty and I) plan to use this as a basis for a new statistical model of language. This work on language is described in two technical reports: CMU-CS-91-196, CMU-CS-92-181.
Competitive Algorithms: Consider the idealized problem of deciding whether to rent or buy skis. You're about to go skiing. The cost of renting skis is $20, the cost of buying them is $400. Clearly if you knew that you were going to go skiing more than twenty times, then you could save money by immediately buying skis. If you knew that you would go skiing fewer than twenty times, then it would be prudent to always rent skis. However, suppose that you cannot predict the future at all, that is, you never know until after one ski trip ends if you will ever go skiing again. What strategy would you use for deciding whether to rent or buy skis? Your goal is to minimize the ratio of the cost that you incur to the cost you would incur if you could predict the future. (Hint: you can come within a factor of two.)
Since the simple principle behind this example turns out to be very useful we have given it a name. A competitive algorithm is an on-line algorithm (it must process a sequence of requests, and it must process each request in the sequence immediately, without knowing what the future requests will be), whose performance is within a small constant factor of the performance of the optimal off-line algorithm for any sequence of requests. (In the skiing example, there is only one type of request, and the only uncertainty is in knowing how long the request sequence will be.)
My collaborators and I have discovered a surprising variety of practical problems for which there exist very efficient competitive algorithms. We have also developed a partial theory of competitive algorithms. However there remain many interesting open problems, from discovering competitive algorithms for specific problems, to answering general questions about when such algorithms exist.
Data Structures: Data structure problems are typically formulated in terms of what types of operations on the data are required, and how fast these operations should take place. A worst-case analysis of the performance of a data structure is a bound on the performance of any operation. An amortized analysis of a data structure bounds the performance of the structure on a sequence of operations, rather than a single operation. It turns out that by only requiring amortized efficiency (rather than worst-case), a variety of new and elegant solutions to old data structure design problems become possible. My collaborators and I have devised a number of such solutions (splay trees, skew heaps, fibonacci heaps, self-adjusting lists, persistent data structures, etc.), and I continue to have a strong interest in data structures and amortized analysis.
Homepages
Contact Information
412-268-7563
