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.)

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.

* Mobile Robot Navigation (Sven Dickenson)

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