Kevin Milans
Future City 1993
Tilden Middle School, Rockville, Maryland

EDUCATION: B.Sci. Carnegie Mellon University, M.Sci., mathematics, University of Illinois at Urbana-Champaign

CURRENTLY: Teaching assistant and Ph.D. candidate at UIUC, researching graph theory, algorithms and combinatorics, specializing in complexities of graph pebbling.

I am a graduate student at the University of Illinois at Urbana-Champaign, studying combinatorics, graph theory, and algorithms.  These disciplines of mathematics and theoretical computer science offer many challenging research problems.  The study of algorithms tries to answer questions about how efficiently we can compute or approximate solutions to computational problems; for example, if we are given two large numbers, how quickly can we multiply them together?  As it turns out, there are faster ways to multiply than the traditional method we all practice in elementary school.  Graph theory studies the relationships between objects.  A famous example is the fact that if six people walk into a room, then either some group of three have met each other before or some group of three meet each other for the first time.

My research has touched on some diverse areas of combinatorics.  One emerging area, known as graph pebbling, has similar elements to the popular game Mancala.  In graph pebbling, pebbles are distributed to vertices of the graph; the vertices of the graph are analogous to the pits of the Mancala game.  In the Mancala game, one is allowed to pick up all the pebbles in a pit and redistribute them by placing one pebble in each of nearest pits in the clockwise direction, until one runs out of pebbles.  In graph pebbling, one is allowed to select two pebbles from a vertex, throw one away, and place the remaining pebble on a neighboring vertex.  In joint work with Bryan Clark, we were able to determine that many natural computational questions that arise in the graph pebbling context are computationally hard.  In fact, the most commonly studied problem in graph pebbling is so difficult that even if one is given access to an impossibly powerful computer known as a Nondeterministic Turing Machine, there is still good reason to believe that solving these problems would be intractably slow.

More information is available at my research web page at
http://www.math.uiuc.edu/~milans/research.html

In addition to research, I work as a teaching assistant for a senior level course in algorithms.  As a member of course staff, I have the opportunity to help future programmers develop the mathematical skills necessary to analyze and improve the programs that they produce.  Additionally, we help tomorrow's programmers recognize when they are attempting to solve problems that most people believe cannot be solved quickly.  In such a case, the programmer may be able to redesign the program to avoid the expensive computation or be satisfied with an approximate solution.