 |
Eli Upfal
Professor of Computer ScienceContact Information
Box 1910Brown University
Providence, RI 02912
Email: eli at cs.brown.edu
Personal home page: http://www.cs.brown.edu/~eli/
Research Areas
| Design and Analysis of Algorithms |
| Computational Biology |
| Parallel Computing |
| Theory of Computation |
| Combinatorial Optimization |
Research Themes
| Statistical Approaches |
Research Topics or Projects
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.
Selected Publications
Anagnostopoulos, A., Kirsch, A., and Upfal, E. Stability and efficiency of a random local load balancing protocol. SIAM Journal on Computing 34 (2005), 616-639. [ pdf ]
Anagnostopoulos, A., Kontoyiannis, I., and Upfal, E. Steady state analysis of balanced-allocation routing. Random Structures & Algorithms 26 (2005), 446-467. [ pdf ]
Pandurangan, G., Raghavan, P., and Upfal, E. Using PageRank to characterize web structure. Internet Mathematics 2 (2005), 217-236. [ pdf ]
Preparata, F., Upfal, E., and Heath, S. Sequence reconstruction from nucleic acid micro-array data. In Analytical Techniques for DNA Sequencing, B. Nunnally, Ed. M. Dekker, 2005, pp. 177-193.
Anagnostopoulos, A., Bent, R., Upfal, E., and Hentenryck, P. V. A simple and deterministic competitive algorithm for online facility locations. Information and Computation 194, 2 (Nov 2004), 175-202. [ pdf ]
Anagnostopoulos, A., Kontoyiannis, I., and Upfal, E. The advantage of balanced-allocation routing for ATM networks. In Proceedings of the IEEE International Symposium on Information Theory (ISIT-2003) (Jun 2003). [ pdf ]
Anagnostopoulos, A., Kirsch, A., and Upfal, E. Stability and efficiency of a random local load balancing protocol. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS) (Nov 2003), pp. 472-481. [ pdf ]
McDiarmid, C., Luzak, M., and Upfal, E. On-line routing of random calls. Probability Theory and Related Fields 125 (2003), 457-482. [ pdf ]
Pandurangan, G., Raghavan, P., and Upfal, E. Building low-diameter peer-to-peer networks. IEEE Journal on Selected Areas in Communication 21 (2003), 995-1002. [ pdf ]
Upfal, E. Tutorial: Performance analysis of dynamic network processes. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (2003). [ pdf ]
Pandurangan, G., Raghavan, P., and Upfal, E. Using PageRank to characterize web structure. In Proceedings of the 8th Annual International Conference on Combinatorics and Computing (COCOON) (2002), pp. 330-339. [ pdf ]
Hauskrecht, M., Ortiz, L., Tsochantaridis, I., and Upfal, E. Efficient methods for computing investment strategies for multi-market commodity trading. Applied Artificial Intelligence 15 (2001), 429-452. [ pdf ]
Pandurangan, G., Raghavan, P., and Upfal, E. Building low-diameter P2P networks. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (2001), pp. 492-499. [ pdf ]
Pandurangan, G., and Upfal, E. Can entropy characterize performance of online algorithms? In Proceedings of the 12th ACM Society for Industrial and Applied Mathematics Symposium on Discrete Algorithms (Jan 2001), pp. 727-734. [ pdf ]
Shavit, N., Upfal, E., and Zemach, A. A wait-free sorting algorithm. Theory of Computer Systems 34 (2001), 519-544. [ pdf ]
All publications by Eli Upfal
| Page Owner: Eli Upfal | Last Modified: Tue Sep 9 10:59:21 2008 |