About

Eli Upfal is the Rush C. Hawkins professor of computer science at Brown University. He served as the department chair from 2002 to 2007. Prior to joining Brown in 1998, he was a researcher and project manager at the IBM Almaden Research Center in California and a professor at the Weizmann Institute in Israel. He holds an undergraduate degree in mathematics and statistics and a doctorate degree in computer science from the Hebrew University in Jerusalem, Israel. His research focuses on the design and analysis of algorithms, with particular interest in randomized algorithms and probabilistic analysis of algorithms. His work has applications in combinatorial and stochastic optimization, routing and communication networks, computational biology, and computational finance. Additionally, he notes his Erdos number is 2 and that he is a mathematical descendant of Eli Shamir, Jacques Hadamard (4th generation), Simeon Denis Poisson (8th generation), and Pierre-Simon Laplace (9th generation).

Research topics

• Machine Learning
• Computer Science
• Artificial Intelligence

Selected publications

• Balanced allocation: considerations from large scale service environments

  arXiv (Cornell University) · 2026-01-15

  preprintOpen accessSenior author

  We study d-way balanced allocation, which assigns each incoming job to the lightest loaded among d randomly chosen servers. While prior work has extensively studied the performance of the basic scheme, there has been less published work on adapting this technique to many aspects of large-scale systems. Based on our experience in building and running planet-scale cloud applications, we extend the understanding of d-way balanced allocation along the following dimensions: (i) Bursts: Events such as breaking news can produce bursts of requests that may temporarily exceed the servicing capacity of the system. Thus, we explore what happens during a burst and how long it takes for the system to recover from such bursts. (ii) Priorities: Production systems need to handle jobs with a mix of priorities (e.g., user facing requests may be high priority while other requests may be low priority). We extend d-way balanced allocation to handle multiple priorities. (iii) Noise: Production systems are often typically distributed and thus d-way balanced allocation must work with stale or incorrect information. Thus we explore the impact of noisy information and their interactions with bursts and priorities. We explore the above using both extensive simulations and analytical arguments. Specifically we show, (i) using simulations, that d-way balanced allocation quickly recovers from bursts and can gracefully handle priorities and noise; and (ii) that analysis of the underlying generative models complements our simulations and provides insight into our simulation results.

  PublisherDOI

• Balanced allocation: considerations from large scale service environments

  ArXiv.org · 2026-01-15

  articleOpen accessSenior author

  We study d-way balanced allocation, which assigns each incoming job to the lightest loaded among d randomly chosen servers. While prior work has extensively studied the performance of the basic scheme, there has been less published work on adapting this technique to many aspects of large-scale systems. Based on our experience in building and running planet-scale cloud applications, we extend the understanding of d-way balanced allocation along the following dimensions: (i) Bursts: Events such as breaking news can produce bursts of requests that may temporarily exceed the servicing capacity of the system. Thus, we explore what happens during a burst and how long it takes for the system to recover from such bursts. (ii) Priorities: Production systems need to handle jobs with a mix of priorities (e.g., user facing requests may be high priority while other requests may be low priority). We extend d-way balanced allocation to handle multiple priorities. (iii) Noise: Production systems are often typically distributed and thus d-way balanced allocation must work with stale or incorrect information. Thus we explore the impact of noisy information and their interactions with bursts and priorities. We explore the above using both extensive simulations and analytical arguments. Specifically we show, (i) using simulations, that d-way balanced allocation quickly recovers from bursts and can gracefully handle priorities and noise; and (ii) that analysis of the underlying generative models complements our simulations and provides insight into our simulation results.

  PublisherOA PDF

• DiNgHy: Null Models for Non-degenerate Directed Hypergraphs

  Lecture notes in computer science · 2025-10-03

  articleSenior author
  PublisherDOI

• Bruisable Onions: Anonymous Communication in the Asynchronous Model

  Lecture notes in computer science · 2024-12-01

  book-chapterSenior author
  PublisherDOI

• An Adaptive Algorithm for Learning with Unknown Distribution Drift

  2023-01-01

  articleSenior author
  PublisherDOI

• An Adaptive Algorithm for Learning with Unknown Distribution Drift

  arXiv (Cornell University) · 2023-05-03

  preprintOpen accessSenior author

  We develop and analyze a general technique for learning with an unknown distribution drift. Given a sequence of independent observations from the last $T$ steps of a drifting distribution, our algorithm agnostically learns a family of functions with respect to the current distribution at time $T$. Unlike previous work, our technique does not require prior knowledge about the magnitude of the drift. Instead, the algorithm adapts to the sample data. Without explicitly estimating the drift, the algorithm learns a family of functions with almost the same error as a learning algorithm that knows the magnitude of the drift in advance. Furthermore, since our algorithm adapts to the data, it can guarantee a better learning error than an algorithm that relies on loose bounds on the drift. We demonstrate the application of our technique in two fundamental learning scenarios: binary classification and linear regression.

  PublisherOA PDFDOI

• Nonparametric Density Estimation under Distribution Drift

  arXiv (Cornell University) · 2023-02-05

  preprintOpen accessSenior author

  We study nonparametric density estimation in non-stationary drift settings. Given a sequence of independent samples taken from a distribution that gradually changes in time, the goal is to compute the best estimate for the current distribution. We prove tight minimax risk bounds for both discrete and continuous smooth densities, where the minimum is over all possible estimates and the maximum is over all possible distributions that satisfy the drift constraints. Our technique handles a broad class of drift models, and generalizes previous results on agnostic learning under drift.

  PublisherOA PDFDOI

• An Adaptive Method for Weak Supervision with Drifting Data

  arXiv (Cornell University) · 2023-06-02

  preprintOpen access

  We introduce an adaptive method with formal quality guarantees for weak supervision in a non-stationary setting. Our goal is to infer the unknown labels of a sequence of data by using weak supervision sources that provide independent noisy signals of the correct classification for each data point. This setting includes crowdsourcing and programmatic weak supervision. We focus on the non-stationary case, where the accuracy of the weak supervision sources can drift over time, e.g., because of changes in the underlying data distribution. Due to the drift, older data could provide misleading information to infer the label of the current data point. Previous work relied on a priori assumptions on the magnitude of the drift to decide how much data to use from the past. In contrast, our algorithm does not require any assumptions on the drift, and it adapts based on the input by dynamically varying its window size. In particular, at each step, our algorithm estimates the current accuracies of the weak supervision sources by identifying a window of past observations that guarantees a near-optimal minimization of the trade-off between the error due to the variance of the estimation and the error due to the drift. Experiments on synthetic and real-world labelers show that our approach adapts to the drift.

  PublisherOA PDFDOI

• Reducing polarization and increasing diverse navigability in graphs by inserting edges and swapping edge weights

  Data Mining and Knowledge Discovery · 2022-10-02 · 3 citations

  articleSenior author
  PublisherDOI

• Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes

  2022-01-01

  article
  PublisherDOI

Recent grants

• Efficient Distributed Approximation Algorithms

  NSF · $25k · 2009–2011

• RI: Small: Statistically Sound and Computationally Efficient Data Analysis Through Algorithmic Applications of Rademacher Averages

  NSF · $466k · 2018–2023

• Analytical Approaches to Massive Data Computation with Applications to Genomics

  NIH · $283k · 2013–2018

• BIGDATA: Mid-Scale: DA: Analytical Approaches to Massive Data Computation with Applications to Genomics

  NSF · $1.6M · 2012–2018

• ITR/SY Algorithmic Issues in Large Scale Dynamic Networks

  NSF · $554k · 2001–2007

Frequent coauthors

• Fabio Vandin

  University of Padua

  78 shared

• Matteo Riondato

  61 shared

• Gopal Pandurangan

  University of Houston

  56 shared

• Benjamin J. Raphael

  49 shared

• Lorenzo De Stefani

  44 shared

• Andrea Pietracaprina

  University of Padua

  40 shared

• Geppino Pucci

  University of Padua

  38 shared

• Ahmad Mahmoody

  Microsoft (Finland)

  32 shared