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.)
- Yuval Ishai - DIMACS Postdoc (Questions on Private Computation)
- Dieter van Melkebeek - DIMACS Postdoc (Efficient Reversible Simulations of Computations)
- Wilma Olson - Chemistry (Computational Chemistry/Biology)
- Endre Boros - Operations Research
- Adi Ben-Israel/Yuri Levin - Mathematics
- Endre Szemerédi - Computer Science
- Chris Woodward - Mathematics
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.
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.