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 and collaborator Michael Mitzenmacher (Harvard) were awarded a $100,000 Yahoo! Research Alliance gift for their research in the same area.
