Proposed projects for the 2000 DIMACS REU Program

Supervisors and Suggested Problems

Faculty Supervisors

The following faculty have expressed interest in participating in the program in 2000. (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.

* Questions on Private Computation (Yuval Ishai)

A private computation protocol allows a group of mutually suspicious players to jointly evaluate a function of their inputs without revealing their inputs to each other. A well studied special case is that of voting, where the goal is to compute the vote tally without sacrificing the secrecy of individual votes. There are several interesting research questions concerning the efficiency of solving specific private computation tasks, where efficiency may be measured in terms of communication, randomness, or amount of interaction.

* Efficient Reversible Simulations of Computations (Dieter van Melkebeek)

A computation is reversible if every step can be undone by another computation. The original motivation for the study of reversible computations came from thermodynamics. Irreversible state changes have to dissipate heat, and heat dissipation forms a major obstacle to the miniaturization of classical computers. In recent years, the issue has regained interest in the context of quantum computing. The classical computations that also run on a quantum computer are precisely the reversible ones.

For these reasons, computer scientists have developed techniques to simulate arbitrary computations in a reversible way. They try to make the reversible simulations as efficient as possible, both time and space wise. We currently know optimal solutions for each of these goals individually: We can reversibly simulate any computation without blowing up the time required by more than a constant factor, and the same holds for space. However, we do not know how to achieve both goals at the same time.

The known optimal solutions are quite neat. The goal of this project is to become familiar with them and to investigate the open problem of combining their features in a reversible simulation that is both time and space efficient.

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

Quadratic programming (Endre Boros)

Quadratic binary optimization is a very difficult problem, in general. A possibility to get good approximations is to construct a ``tight'' convex majorant. Such tight majorants are known for functions depending on 2 variables, but even for 3-variable functions, such convex majorants are not well described.

This project will aim at developing a method of constructing such majorants, and perhaps even to characterize those for small functions, depending on 3,4 or 5 variables.

*Chris Woodward

A central topic in mathematics, and more recently in physics, is symmetry, and in particular, how symmetries behave under "combination". To give a simple example, consider a function f(x) in one variable. f(x) is called even if f(x) = f(-x), odd if f(x) = - f(-x). The product of two even (resp. odd) functions is even, while the product of an even and odd function is odd.

The goal of this project is to investigate a new combinatorial rule for determining the generalization of this rule to higher dimensions. Let S_n be the symmetric group of permutations of the variables x_1,....,x_n. How do product of functions of x_1,...x_n behave, with respect to the symmetric group, under multiplication? (The case of two variables is equivalent to the case discussed in the previous paragraph.)

In 1998 Knutson and Tao gave a new combinatorial rule for the break-up of two functions, which in many respects is more useful than the rule of Littlewood and Richardson. Possible extensions include generalization to more than two functions, and two other types of combinatorial problems such as Schubert calculus for the full flag variety. However, further developments in this field are likely before the summer begins, and the last part of the project will have to be modified somewhat.

This page was last modified on January 18, 2000.