Eli Upfal And Co-Authors Win A STOC 30-Year Test Of Time Award
- Posted by Robayet Hossain
- on Sept. 7, 2024
The Annual ACM Symposium on Theory of Computing (STOC), held since 1969, is widely considered one of the two most important conferences in the field of theory of computing. This year, a 1994 paper by Brown CS faculty member Eli Upfal received the conference’s 30-year Test of Time Award. His co-authors include Yossi Azar (Professor of Computer Science at Tel-Aviv University), Andrei Z. Broder (Distinguished Scientist at Google), and Anna R. Karlin (Bill and Melinda Gates Chair in Computer Science and Engineering at the University of Washington, Seattle).
According to the STOC Awards Committee, “Azar, Broder, Karlin, and Upfal considered the natural balls-and-bins load-balancing problem in which they pioneered the power-of-two-choices paradigm, in which two bins are chosen uniformly at random, and then the next ball is placed in the currently less loaded one. In placing nn balls in nn bins, this yields, with high probability, a solution in which the most loaded bin has only [lnlnn/ln2 + O(1)lnlnn/ln2 + O(1) balls], an extraordinarily surprising exponential improvement on the result of placing the balls uniformly at random. This spurred a long line of research in which the analogous approach was applied, with similarly strong results, in much more general settings, and remains one of the most effective algorithmic load-balancing tools.”
“Receiving the email about the award, one of my co-authors’ reactions was ‘are we really that old?’” says Eli. “Well, yes. This paper was published in STOC 1994!”
Eli’s research focuses on the design and analysis of algorithms, emphasizing randomized algorithms and probabilistic analysis of algorithms. The applications of his work range from communication networks to computational biology and finance. This past May, four of his former PhD students put together FestivEli, a celebration of his contributions and accomplishments throughout the years.
This award follows Eli’s 2023 RECOMB Test-Of-Time award for work on mutated driver pathways in cancer. He joins Brown CS faculty member Philip Klein, who won the STOC Test-Of-Time award last year.
For more information, please click the link that follows to contact Brown CS Communications Manager Jesse C. Polhemus.
