Eli UpfalProfessor of Computer Science
Contact InformationBox 1910
Providence, RI 02912
Email: eli at cs.brown.edu
Personal home page:
|Design and Analysis of Algorithms|
|Theory of Computation|
|CSCI1570||Design and Analysis of Algorithms|
|CSCI1550||Probabilistic Methods in Computer Science|
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.