ATTENTION: THIS WEB SITE HAS MOVED.
The pages you are looking at are no longer being maintained.
Please go to http://www.poly.edu/cis/
to visit the new site of the Department of Computer and Information Science
at Polytechnic University.
Algorithms and Complexity
(Profs. Aronov,
Brönnimann, Chiang,
Hellerstein, Suel,
van Slyke,
Wein)
The department has significant research strength in the algorithms
area, with about half of our current faculty being actively involved
in work ranging from fundamental theoretical problems in complexity
to the experimental evaluation of algorithmic techniques.
Computational Geometry: Several faculty members are working on
problems in the area of Computational Geometry, which is concerned
with fundamental techniques for computing with geometric objects,
and forms the theoretical basis for much work in applied areas
such as Computer Graphics and Vizualization. In particular, Prof.
Aronov has been studying a variety of questions in Combinatorial
Geometry, i.e., the study of the combinatorial properties and
resulting fundamental complexities of geometric problems. Prof.
Brönnimann's work is concerned with theoretical issues in
Computational Geometry as well as with practical problems arising
in the context of programming libraries and object-oriented techniques
for geometric computing. Prof. Chiang is studying geometric problems
in graphics and visualization, with emphasis on I/O-efficient
techniques for processing massive geometric data sets.
Approximation Algorithms & Combinatorial Optimization:
Research in this area is concerned with precise and approximate
solutions to hard algorithmic problems arising in many real-world
situations, such as the optimal design of computer networks and other
infrastructure, the scheduling of tasks to ensure the efficient use
of limited resources, or the partitioning of data and work between
nodes of a parallel machine. Two faculty members in our department,
Profs. van Slyke and Wein, primarily focus on problems in this area.
Prof. van Slyke has extensively worked on problems in combinatorial
optimization theory and the design of information networks; among
his recent works is a new distributed version of the simplex method,
and a non-cooperative game model of flow control in computer networks.
Prof. Wein has focused on scheduling and resource allocation problems,
including general conversion techniques for transforming off-line
into on-line scheduling algorithms, task scheduling in generalized
communication networks, combinatorial problems in scheduling
independent jobs in parallel machines, efficient algorithms for the
dense assignment problem, and fractiling in parallel computation.
Several other faculty members have also worked on approximation
algorithms for a variety of flow, partitioning, and geometric problems.
Computational Learning Theory: Prof. Hellerstein is working
on fundamental problems in the area of Computational Learning Theory,
an area concerned with algorithms and fundamental limits for machine
learning. Much of Prof. Hellerstein's work concerns query models of
learning, in which the learner can ask questions of a teacher or can
perform experiments. She has developed a number of efficient
algorithms for learning particular classes of concepts in query models.
She has also developed new techniques for determining when a class
of concepts is learnable in query models, and for designing
algorithms that remains efficient in the presence of irrelevant
information. Prof. Hellerstein is particularly interested in the
learnability of classes of Boolean functions and has done related
research on characterizations of Boolean function classes. Recently,
Prof. Hellerstein has also begun working on learning-based approaches
in information retrieval.
Parallel and Distributed Algorithms:
This area is concerned with the design of efficient algorithms for
massively parallel machines, networks of workstations, and wide-area
distributed networks. Two faculty members, Profs. Suel and Wein,
have worked extensively in these areas. Prof. Suel's research has
been concerned with the theoretical foundations of fixed-connection
networks, such as meshes, hypercubes, or other types of graphs, and
he has shown fundamental upper and lower bounds for sorting and
communication problems on these networks. Another area of interest
to him are models of parallel computation that allow and encourage
the design of programs that are efficiently portable among different
parallel architectures. Prof. Wein's research in this area is
concerned with load balancing and partitioning techniques that
schedule computations in a distributed environment in ways that
perserve the locality properties of the underlying problem and adapt
to changes in resource availability. Both faculty are also working
with colleagues to apply their algorithmic results to real-life
parallel computing problems, including simulations of particle and
semiconductor physics, signal propagation, and nuclear stockpile
testing.
