Proposed projects for the 1999 DIMACS REU Program
Supervisors and Suggested Problems
Faculty Supervisors
The following faculty have
expressed interest in participating in the program in 1998-99.
(Other faculty and project areas may be added later.)
The suggested area of research appears in parentheses.
(Note: RUTCOR is the Rutgers Center for Operations Research.)
- Michael Krivelevich - DIMACS Postdoc (Extremal Problems on Color-Critical Graphs)
- Alex Samorodnitsky - DIMACS Postdoc (Chromatic Polynomials in Random Graphs)
- Eric Allender - Computer Science (Arithmetic Circuits and Branching Programs)
- Sven Dickenson - Computer Science (Robotics)
- Wilma Olson - Chemistry (Computational Chemistry/Biology)
- Bill Steiger - Computer Science (Depths of Point Sets)
- Chuck Weibel - Mathematics (Convergence Rates for Interior Methods in Linear Programming)
- Avigdor Gal - Management Science and Information Systems (Obsolescence Factors in Query Processing)
Suggested Projects
The following topics have been suggested by REU
research supervisors, and offer a range of both applied and
theoretical problems. The topics are of current interest to Computer
Scientists and Mathematicians, but can be understood in a short period
of time by a well-trained undergraduate. Supervisors may also be
willing to work on other topics, depending on the student's and their
own interests.
* Extremal Problems on Color-Critical Graphs (Michael Krivelevich)
A graph G is k-color-critical if it has chromatic number k, but every
proper subgraph of it is (k-1)-colorable. The importance of the
notion of color-critical graphs follows from the simple
observation that every graph of chromatic number k contains a
k-color-critical subgraph. Therefore, understanding critical
graphs may prove very helpful in many graph coloring problems.
Here is an example of an extremal problem about critical graphs
which stands unsolved for about 40 years: what is the minimal
possible number of edges in a k-critical graph on n vertices?
Extremal problems on color-critical graphs are a very fascinating
subject by itself, but they can lead to new and important results in
other fields of Graph Theory, such as Extremal Graph Theory, Ramsey
Theory, Random Graphs.
* Chromatic Polynomials in Random Graphs (Alex Samorodnitsky)
What do we know about the chromatic polynomial
of random graphs? Bollobas' work tells us where its first
non-root is (i.e. what is a chromatic number of a random graph)
but one can hope to get much more information. Specifically, to what
extent are the polynomials concentrated? There are many specific
subproblems that one may ask, e.g.: the chromatic polynmial evaluated
at -1 equals the number of acyclic orientations of the graph.
What can we say about the distribution of this random variable?
* Arithmetic Circuits and Branching Programs (Eric Allender)
Complexity theory groups computational problems into
classes having similar computational complexity. A
fundamental problem is to determine which problems lie in
which complexity classes. Recently, algebraic techniques
have been used to classify the complexity of problems that
have low complexity in the Boolean circuit model, and this
in turn motivates questions about arithmetic circuits and
branching programs. In particular, some very interesting
open questions in circuit complexity can be posed in terms
of multiplying sequences of 2-by-2 and 3-by-3 integer matrices.
Some questions in this direction are appropriate for an
undergraduate research project.
A key problem in mobile robotics is to find a way to program a mobile
robot (equipped with a camera) to visually navigate its environment,
i.e., visually determine its position (coordinates). A promising
approach is to have the robot first determine the optimal set of
visual landmarks for navigation, and then use these landmarks to
compute its position. The problem of finding the optimal set of
landmarks can be formulated as a graph coloring problem with special
constraints introduced by the nature of the problem. The goal of this
project is to design, implement, and/or test algorithms to solve this
problem.
In order to test both landmark acquisition and navigation algorithms,
an environment simulator is needed in which indoor environments with
different shapes, obstacles, and landmarks can be created. The
student's role in this project will be to design and implement (in
software) such an indoor environment simulator. This will not only
include exposure to computational geometry algorithms, but to computer
graphics techniques as well. Once the simulator is complete, the
student will test various landmark acquisition algorithms using the
simulator, and, if time permits, promising approaches will be tested
on a mobile robot operating in a mock-up nuclear reactor in Canada.
Students with an interest in graph theory and graph algorithms are
encouraged to apply. A background in algorithm design and programming
experience in C would be be very useful. In addition, the design of
the simulator offers interesting problems in computer graphics.
Note: This project will build upon previous projects. See, for
example, David
Rosenberg's project.
* DNA Sequences and Three-dimensional Structure (Wilma Olson)
The DNA base sequence, once thought to be interesting only as a carrier
of the genetic blueprint, is now recognized as playing a structural role
in modulating the biological activity of genes. Through subtle
variations of bending and twisting at the level of neighboring base
pairs, the chemical sequence not only generates a higher-order folding
of the double helix itself but also produces structural motifs that
facilitate the specific binding of proteins and other ligands. The
consequent looping and twisting of the DNA assumes an important role in
various biological processes.
To understand how the genetic code is translated into three-dimensional
structures used in biological processes, our group is analyzing the
known geometry of DNA bases in chemical structures and developing
mathematical models to incorporate the sequence-dependent bending,
twisting, and translation of known fragments in DNA molecules of varying
lengths and chemical composition.
Note that this year's project will build on the successes of previous
students who worked with Prof. Olson on this project. See, for
example, Lynette Hock's
project.
* Depths of Point Sets (Bill Steiger)
Given n numbers, a_1, ... ,a_n, the sorted order
provides a natural notion of depth, whereby for real numbers x, the depth
of x is the minimum of |{i:a_i <= x}| and
|{i:a_i >= x}|; a median is a point of maximal depth. Several
interesting definitions of depth given points in d-dimensional space
have been
proposed. There are many open questions concerning the
combinatorics and computation of these depths.
* Convergence Rates for Interior Methods in Linear Programming (Chuck Weibel)
There are two main techniques for solving a linear programming problem
using "interior" methods: Log. Barrier methods and Potential Methods
(e.g., Karmarkar's Algorithm). Both methods begin with an initial
solution x0 inside the feasable region, and iterate towards the solution.
The project is to investigate how the convergence depends upon the
choice of the initial solution x0.
As a test case, consider the problem of finding the point in the (x,y) plane
which maximizes x, subject to the constraint that the point lie inside
a polygon with 100 sides. Near the boundary, convergence can take
about 25 iterations (25 is n/4 for an 100-gon), but near the middle convergence
is much more rapid (about 8, or log(n) steps).
Probem 1: Does the boundary between rapid and linear convergence look
like a fractal set? How about as n increases?
Problem 2: Compare the trajectories of the two methods.
No one has ever implemented the potential method so the first step in
this project would be to write a simple computer program to use the
potential method on an n-gon. The mathematical sophistication required
of the undergraduate would be at the Calculus III level.
* Obsolescence Factors in Query Processing
(Avigdor Gal)
In recent years query processing has become more complex, as data sources
are frequently replicated and data is periodically processed and embedded
within several data sources simultaneously. Following this trend, it is
significantly important to enhance the optimization techniques for query
processing in order to capture these new alternatives. In particular, an
improved query optimization technique should be able to assess query plans
that use both current and obsolescent data.
This project is aimed at designing an estimation method for the quality
of obsolescent data. The method uses a stochastic approach towards the
estimation of information deterioration. In this project, the student
will evaluate various methods for estimating information deterioration.
Based on the student's skills, the project may also include a programming
component.
This page last modified on December 2, 1998