Eli Upfal

Eli Upfal

Professor of Computer Science

Contact Information

Box 1910
Brown University
Providence, RI 02912
Email: eli at cs.brown.edu
Personal home page:

Research Areas

Design and Analysis of Algorithms
Computational Biology
Parallel Computing
Theory of Computation
Combinatorial Optimization

Courses Taught

CSCI1570   Design and Analysis of Algorithms
CSCI1550   Probabilistic Methods in Computer Science

Research Interests

Eli Upfal’s general research area is theory of computation—trying to apply rigorous mathematical tools to the design and analysis of computer algorithms. He is particularly interested in applications of probability theory and combinatorics to this area. Randomness comes up in two aspects of the study of algorithms: randomized algorithms and probabilistic analysis of algorithms. Randomized algorithms are algorithms that make random choices during their execution. In many cases the randomized algorithms are more efficient, simpler and easier to program than their deterministic counterparts. Probabilistic analysis of algorithms attempt to characterize the average-case performance of algorithms on typical inputs. This issue is important in computation problems for which there are no efficient solutions for all possible inputs.

Recent work includes: Developing probabilistic techniques for studying the long-term behavior of dynamic computer processes such as communication, load balancing, cashing, and paging; a novel combinatorial design improving the design of sequencing by hybridization (SBH) microchips; and stochastic analysis of commodity trading strategies.

All publications by Eli Upfal