Eli Upfal was recently awarded a substantial research grant from Yahoo! for his research on algorithms for large-scale stochastic data. He intends to develop a theoretically well-founded framework for the design and analysis of algorithms for a number of large-scale web-related applications. The primary efforts of this work will focus on two areas:

1) Computing global properties of dynamic structures, such as efficiently maintaining a close to minimum spanning tree in a network, when edge weights are dynamically changing according to some stochastic process; and 2) Developing and analyzing tools for decision-making in a stochastically changing environment. In 2006, Eli ...