MERRICK FURST
PROFESSOR, COMPUTER SCIENCE
ASSOCIATE DEAN
I am interested in internet-based tools for resource discovery and
information exchange. My research project, Six Degrees of Separation,
is developing a distributed information exchange. The central premise
behind the 6DOS exchange is that the National Information
Infrastructure provides an opportunity for a new market for information
exchange, in which individuals and organizations with problems can be
efficiently connected to people and information that provide solutions.
From a recent proposal: "The 6DOS system will rely on several
characteristics of computer networks and human groups: (1) a chain of
less than six people typically connects any person with a question to
the appropriate person with the answer, (2) the NII can provide the
substrate for communication, bookkeeping, and money exchange that will
enable and motivate these chains of people to form and collaborate, (3)
software for routing questions and caching answers to routine questions
can significantly augment this network of human contacts, and (4)
motivation for people to participate in the routing and answering of
questions will be provided by a combination of money exchange, reliance
on personal contacts, and altruism."
I am also interested in establishing connections between computer
science and mathematics with the goal of developing new computational
tools and methods. I work on discovering new algorithms and
understanding the inherent complexity of fundamental computational
problems. I also work on graph-theoretic algorithms, problems in
circuit and algebraic complexity, applications to parallel computation
and theoretical aspects of machine learning theory.
In complexity theory I mainly work on the complexity of representing
functions as circuits. This approach holds the most promise, of all
current approaches, for resolving the P versus NP problem. In this
work, many beautiful mathematical methods are employed, for example:
the combinatorics of probabilistic restrictions, counting arguments,
algebraic decompositions, geometric arguments and communication
complexity.
I am also developing a new approach to the Artificial Intelligence
Planning Problem with Avrim Blum. He and I are studying a new
representation of plans which appears to make the exponential search
for plans more manageable. So far the implementations show great
promise.