Main research interests include parallel algorithms and languages
My main research interests are in machine learning theory, on-line
algorithms, and approximation algorithms.
Machine Learning Theory.
Machine learning theory aims to provide a mathematical analysis of, and
algorithms for, the problems and issues that arise in getting machines to
learn from experience. One issue I have been investigating is the
following that comes up in concept learning. Suppose in the learning
scenario there are many potential features or attributes that examples
might have, even though each individual example has only a few of them.
Can one produce algorithms whose performance depends only on the size of
the examples and not on the size of the entire feature space? Also, what
if only a small number of features are actually relevant to the function
being learned? Under what conditions can one quickly hone in on the
relevant features? I have been working on theoretical models that bring
out these issues, and on algorithms that solve these problems for some
simple concept representations. A second direction I have been working
on is learning concepts that change over time, and finding algorithms
that can quickly adapt to such changes.
In the area of on-line or competitive algorithms I am particularly
interested in theoretical problems of scheduling and path planning in
unknown environments. These problems often involve examining the
following issue: how do you trade off the cost of exploring versus the
costs associated with not exploring and then having, perhaps, to back up
from a wrong decision? In work with Prabhakar Raghavan and Baruch
Schieber at IBM, we were able to provide good algorithms for the problem
of traveling from a start to a destination in an unmapped plane filled
with oriented rectangular obstacles (the robot does not know the
positions of the obstacles and only finds out when the obstacles are
encountered). There are many important open problems in this area, such
as how to make good use of partial prior knowledge, and how to use
randomization to beat known deterministic approaches.
Many important problems turn out to be NP-hard, implying it is unlikely
there will be algorithms for them that are both efficient and optimal in
the worst case. However, for a large number of such problems there are
fast algorithms that find solutions close to optimal, or that can be
shown will find optimal solutions for large classes of instances (e.g.,
random instances). Two problems in particular that I have been
interested in are the classical graph coloring problem and an NP-hard
string-matching problem motivated by issues in DNA sequencing. The
latter is the following problem: given a collection of strings of
characters, find the shortest superstring that contains each string as a
consecutive block. We (myself and several collaborators) were able to
show that a simple and commonly used greedy procedure achieves provably
good worst-case bounds, thus providing some theoretical justification for
past experimental evidence. One open problem I am currently thinking
about is whether there might be a different algorithm for which one could
show even better bounds.
I am interested in the performance analysis and design of computer
systems, particularly distributed systems. I work on finding
analytical models which capture the important characteristics of a
computer system and allow me to redesign the system to improve its
I believe that many fundamental conventional wisdoms on which we base
system designs are not well understood and sometimes false, leading to
inferior designs. One problem is that many of our existing beliefs
stem from analysis which is based on Markovian workloads
(exponentially-distributed job sizes). However todays measured
workloads show much greater variability in job sizes than previously
assumed and furthermore show heavy tails. In light of current
empirical measurements, my research challenges existing age-old
heuristics. Here are just a few examples:
Problem areas I currently work in include: Web server design and implementation,
distributed Web servers, distributed supercomputing servers , routing and scheduling in networks .
My research interests include: speech and natural language processing,
statistical learning algorithms, applied
probability and information theory, algorithms for finite groups.
My research area is parallel algorithms and architectures. For the past
few years my research has focused on how to build the communications
system that underlies a parallel computer. My goal has been to develop
mechanisms for moving data between processors (or between processors and
memory) that are both practical and provably effective. To this end, I
have designed, analyzed, and implemented algorithms for routing, sorting,
and tolerating faults in parallel computers. Most of this work has been
Parallel algorithms and architectures is an area in which there is a lot
of synergy between theory and practice. While the practice of parallel
computing has suggested many problems for theoreticians to tackle, the
theory has had an impact on the practice as well. For example, the
theory of area and volume-universal routing networks motivated the use of
a fat-tree interconnection network to route data between processors in
the Connection Machine Model CM-5 supercomputer. As another example,
extensive experiments indicate that the fastest way to sort on a
Connection Machine Model CM-2 is to use a ``Samplesort'' algorithm, which
is based on a pair of theoretical sorting algorithms due to Huang-Chow
Recently, a new paradigm has been suggested for parallel supercomputing.
Instead of constructing a special-purpose interconnection network for
each parallel computer, the idea is to use high-speed networking
technology to connect a collection of processors or workstations.
Examples of this technology include ATM switches and HIPPI channels.
Although this technology was originally developed for routing telephone
calls, in principle there is no reason why it cannot be used to route
messages between processors or workstations in a parallel or distributed
computer. One of the advantages of using this technology for parallel
computing, rather than building special-purpose communications networks,
is that independent of the market for parallel computers, the technology
will be developed by the telecommunications industry.
Many of the tasks that arise in the context of special-purpose networks
also arise in the high-speed networking setting. There are important
differences, however. In the special-purpose networks domain, the
designer of a routing algorithm has much tighter control over the network
and can make strong performance guarantees. For example, the algorithm
may guarantee that the maximum number of packets queued at any node will
never be large or that the maximum delay experienced by any packet will
never be large. In the high-speed networking domain, the network may
come with only weak performance guarantees. For example, the topology of
the network may be irregular, or the network may not guarantee to deliver
its packets. The designer of a routing protocol for one of these
networks is more concerned with issues such as deadlock, or what to do if
a message never reaches its destination. On the other hand, some of the
techniques that have already developed for special-purpose networks may
be even more applicable in the high-speed networking domain. For
example, although we know several techniques for tolerating faults in a
network such as a butterfly, in practice these faults rarely occur. In a
high-speed networking environment, however, links may be much less
reliable. Similarly, congestion (or ``hot spots'') may be much more
pronounced in a network with irregular topology.
My latest plan is to study the theory behind using high-speed networking
technology to support parallel supercomputing. I'm hoping to find the
same synergy between theory and practice in this realm that I found when
studying special-purpose networks.
My main interest is in algorithm design and parallel computation. For
the last several years I have worked on fine-grain parallel algorithm
design. The main goal is to find parallel algorithms for problems which,
naively, seem to require a sequential one. The hope is two fold. First,
we find algorithms which are much faster than sequential algorithms
without using too many processors. Many parallel algorithms are known
which have much faster parallel running times but they use many more
processors. Thus, the goal is to decrease the time T without
substantially increasing the processor-time product PBT. The processor-
time product is also known as the work. Second, these new algorithms
should uncover fundamental paradigms which will be applicable to a wide
class of problems.
We enumerate some of the ongoing projects:
Sparse Matrix Calculations.
Possibly one of the most fundamental computational intensive operations
performed on a computer is finding solution to linear systems Ax = b. One
can either solve the system by using an iterative method, obtaining an
approximate solution, or directly obtaining an exact solution. In this
discussion we restrict our attention to direct methods, but a similar
approach holds for certain iterative methods as well. If the matrix A is
dense, i.e., most of the entries are nonzero, then sequential and some
parallel methods use n³ work. But if the matrix A is sparse in a nice way
then much better bounds are known on the amount of work needed. The
basic idea is to view A as the incidence matrix of a graph G. In the
case when G is a planar graph we can use the fact that every planar graph
has a separator of size O(Vn). Thus one obtains sequential and parallel
methods for solving these linear systems in approximately n³´² work. A
separator for a graph is a subset of vertices whose removal separates the
remaining graph into two roughly equal size disconnected graphs. We have
produced and are still investigating algorithms for finding efficient
separators for planar graphs.
Graph Separators in 3-Dimensions.
As discussed above, graph separators have many applications. Our main
goal is to determine which graphs have small separators and construct
efficient algorithms for finding these separators. As a corollary to the
fact that planar graphs have O(Vn) separators one gets O(Vn) separators
for such planar graphs as the Voronoi diagram and the Delaunay graph in
2-dimensions. We are presently trying to determine whether or not Voronoi
diagrams in 3-dimensions have small separators, O(n²´³) size. We have
been able to show that many important and natural graphs in 3-dimensions
have O(n²´³) separators. In particular, we have shown that a k-nearest
neighborhood graph has O(n²´³). Other graphs with small separators in
3-dimensions include several natural graphs associated with the
finite-element method in numerical analysis.
Parallel Algorithm Design.
In general we have produced many different and varied parallel
algorithms. One important paradigm which we have found and are still
using today is known as parallel tree contraction. The basic idea is to
find a tree in the underlying structure of the problem and simply
contract it in parallel. In a graph the tree might be a spanning tree and
in a parsing problem it might be a parse tree. An extremely large number
of problems can be efficiently parallelized using parallel tree
My main (closely related) fields are computational game theory and
computational social choice. I am broadly interested though in many areas
of artificial intelligence and theory of CS, including multiagent systems,
approximation algorithms, machine learning, decision making under
uncertainty, and human computation.
My main research areas are in complexity theory, cryptography,
combinatorics, and probability. I am also interested in inference,
learning theory, and randomized algorithms. I love counter-intuitive
Here is a list of questions I find interesting (and which I am unable to
My main research interests are in market design, game theory, optimization (integer programming, search, stochastic optimization, and convex optimization), mechanism design, electronic commerce, artificial intelligence, multiagent systems, auctions and exchanges, automated negotiation and contracting, equilibrium finding, algorithms for solving games, markets for advertising, kidney exchange, voting, coalition formation, preference elicitation, normative models of bounded rationality, resource-bounded reasoning, computational economics, privacy, machine learning, multiagent learning, and networks.
Many of our systems have been commercially fielded.
The following are just some examples of my current projects:
Solving Games, Poker.
We design algorithms for abstracting games and algorithms for solving for the equilibrium of a game, i.e., the best way to play it. For example, we have developed a lossless abstraction algorithm that enabled us to exactly solve poker games over 10,000 times larger than the largest solved previously. Our algorithms have also yielded some of the best poker playing programs for Texas Hold~em. We are also developing opponent modeling and exploitation techniques. Our work also involves complexity analysis and developing new game-theoretic solution concepts.
Expressive Auctions and Exchanges.
We are developing the theory and methodology of how one should design markets when the participants have rich preferences over outcomes. One of my startups has fielded 800 of the most combinatorial markets ever developed, with a trading volume of over $60 billion.
Advertising Markets and Electricity Markets.
We are developing techniques, and founded a new startup company, in the space of expressive advertising markets, such as for TV and online advertising. We may also apply the approaches to electricity markets.
We have developed the market designs and algorithms that run the nationwide kidney exchange at UNOS. Our current research focuses on developing better models and algorithms for the dynamic problem.
Search and Integer Programming.
For example, how should those tree search algorithms branch? Also, we are developing techniques for automated and recursive decompositions.
Revenue Maximization and Automated Mechanism Design.
We are pioneering the idea of using optimization algorithms to automatically design the rules of a game (such as an auction) so that the designer's objective is maximized even though the participants play based on self-interest. An example application is revenue-maximizing combinatorial auctions. Another example is channel abstraction (bundling, automated item definition), such as in TV and Internet display advertising.
Mechanisms for Computationally Limited Agents.
If agents are computationally limited, how should they allocate their deliberation? What should good mechanisms (e.g., auctions) look like for such agents? It turns out that sometimes mechanisms that lead to greater systemwide good can be designed for computationally limited agents than unlimited ones!
You can check out my papers via my home page.
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
I (jointly with coauthor 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.
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, the it would be prudent to always rent
skis. However, suppose that you can not 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
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 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.
Interactive Network Games:
I wrote and maintain the internet chess
server. This very popular service allows people from all over the world
to play chess, observe others playing, and communicate with each other in
various ways. A rating is computed for each player as a function of his
or her performance. You can try it yourself with ``telnet ics.uoknor.edu
Research has theoretical and algorithmic aspects. The former revolves
mainly around polyhedral combinatorics, that is, attempts at describing
various combinatorial structures by systems of linear inequalities.
Recent examples are the polyhedral characterization of the convex hull
of incidence vectors of perfectly matchable subgraphs of a graph; and
the identification of new families of facets of the asymmetric
traveling salesman polytope, the three-index assignment polytope and
the job shop scheduling polyhedron. Another line of research involves
the characterization of classes of graphs for which the maximum-weight
clique problem(NP-complete in general) is polynomially solvable.
Several such classes have let to improved algorithms for the
maximum-weight clique problem on arbitrary graphs. Other algorithmic
results include efficient solution or approximation methods for the 0-1
knapsack problem, the asymmetric traveling salesman and the prize
collecting traveling salesman problems, set covering, traffic
assignment in communication satellites, the minimum makespan problem of
job shop scheduling, etc.
Current research is in combinatorial optimization and graph theory,
with emphasis on the algorithmic aspects. In graph theory, a problem on
the factorization of graphs stated by Lovasz is shown to be solvable in
polynomial time. Current focus is on the study of perfect graphs,
balanced 0,1 matrices and the max-flow min-cut property. Another line
of research deals with NP-hard combinatorial optimization problems
through the study of relaxations. Using polyhedral combinatorics,
contributions are made to the theory of the set covering, location,
vehicle routing and traveling salesman problems.
Primary research interests involve the application of operations
research techniques to logical inference and related areas. These
include inference problems in propositional logic, probabilistic logic,
Bayesian networks and predicate logic, as well as problems in logic
circuit verification and machine learning. Hooker's approach is to
exploit the mathematical structure of logic problems, such as the
polyhedral structure of propositional logic. He also has interests in
transportation problems and optimal location on networks, as well as in
the philosophical presuppositions of artificial intelligence.
My current research focuses on developing tractable relaxations and
efficient algorithms with strong theoretical performance guarantees
for solving challenging large scale optimization problems under uncertainty
with applications in compressed sensing, high dimensional statistical
inference and machine learning. I also have done research on real-time
decision making and discrete optimization. Overall, I have a strong interest
for providing quantitative methodologies to aid decision making in complex
operational settings such as inventory and supply chain management, production
planning and scheduling and revenue management while taking into account
dynamic and competitive nature of operations and uncertainties in data.
My research interests are concerned with the mathematical and computational
optimization algorithms, especially interior-point methods for convex
Currently, I am investigating properties of condition numbers for linear
programming. Like traditional condition numbers for linear equations, these
numbers aim to capture how changes in the data of the linear program affect
properties of the solutions. The study of condition numbers lies in the
intersection of optimization and numerical analysis; it combines ideas from
interior-point methods, convex analysis, perturbation theory, and complexity
Research interests include approximation algorithms, combinatorial optimization, and computational biology.
Michael Trick's Operations Research Page.
Research is in combinatorial and network optimization. Recent work has
been on computational aspects of integer and network optimization along
with data structures for efficient implementation. Current research has
concentrated on hard integer programs with underlying network
structures. Also interested in the application of algorithm design and
complexity theory in the social and biological sciences.
My research is in extremal
and probabilistic combinatorics; in particluar, recent work
has been on additive number theory, the Shannon capacities
of graphs, the combinatorics of cellular automata, random
graphs and randomized algorithms. Shannon capacity is a
prime example of the close link between extremal
combinatorics and information theory. This graph
invariant arises as a measure of the zero-error perfomance
of an associated noisy communication channel but leads to
very natural (and notoriously difficult) questions in
extremal combinatorics. The aim of the work on cellular
automata is not the study of models that have particular
applications to other scientific fields (there are many
such applicable models, but very few of them have
succumbed to rigorous mathematical treatment) but rather
to study those models that appear most ameniable to
mathematical analysis, with the goal of developing methods
that can be applied to other, more intricate models.
There is no ugly mathematics, only
mathematics that I do not understand. Some mathematics not only I do
not understand, but I do not understand why I do not understand. For
some I do not even understand why nobody understands. That latter kind
is the mathematics that I like to work on. Thus far, this led me to
working on a variety of problems that are a mix of combinatorics,
geometry, and number theory. The concrete problems change often, so to
learn what I do now, knock on my office door!
Research interests lie in combinatorics, discrete optimization and
theoretical computer science. Current focus is on probabilistic
aspects, in particular, the study of the asymptotic properties of
random graphs and the average case analysis of algorithms. Recent work
has been on a randomized algorithm for approximating the volume of
convex bodies, the Hamilton cycle problem in various models of a random
graph and the use of martingale inequalities in the study of random
graphs. I have also been working on exact algorithms for NP-hard
problems with a good average case performance. I also have a strong
interest in complexity theory.
I am interested in problems that lie at the vibrant intersection of Combinatorics, Probability, and Theoretical Computer Science. These include questions in Ramsey Theory (and more generally Extremal Combinatorics), where the Probabilistic Method has found many surprising applications in otherwise deterministic settings. My work also considers discrete systems that are inherently probabilistic, from static structures such as random graphs to dynamic processes such as randomized algorithms and combinatorial games. As these fields are closely related, there is much opportunity for developments from one side to find applications in another.
Principal research interests lie in the theory of computation with
special emphasis on symbolic computation. In particular, current
research involves lambda calculus and combinatory algebra. This area
underwent extensive development in the first half of this century, and
then lay dormant until Dana Scott's fundamental work in the 1970s. Part
of what has emerged from Scott's work is that lambda calculus forms the
foundation of functional programming at both the semantic and syntactic
levels. The area has been revived by an influx of theoretical problems
directly related to design and implementation issues.