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.