Melissa Gould, Kleinberg (Small Mountain), 1992.

Robert D. Kleinberg

Professor of Computer Science, Cornell University

317 Gates Hall
Department of Computer Science
Cornell University
Ithaca, NY 14853

Telephone: 607-255-9200
Fax: 607-255-4428
email:

Ph.D. Students

Ramiro Deo-Campo Vuong
Erald Sinanaj

Former Students

Bruno Abrahao
Hyung-Chan An (co-advised with David Shmoys)
Makis Arsenis
Ashwinkumar Badanidiyuru
Anna Blasiak
Hu Fu
Raunak Kumar
Rad Niazadeh
Princewill Okoroafor
Ayush Sekhari
Yogi Sharma (co-advised with David Williamson)
Tegan Wilson
Yang Yuan

Postdocs

Yoav Kolumbus

Former Postdocs

Saeed Alaei
Thomas Kesselheim
Patrick Briest
Shahar Dobzinski
Katrina Ligett

Teaching

CS 4820: Introduction to Analysis of Algorithms
Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2014, Spring 2017, Spring 2018, Spring 2019, Spring 2021. Spring 2024.

CS 4850: Mathematical Foundations of the Information Age Spring 2022

CS 6820: Analysis of Algorithms
Fall 2008, Fall 2010, Fall 2012, Fall 2013, Fall 2016, Fall 2017, Fall 2018, Fall 2019, Fall 2020, Fall 2021, Fall 2023.

CS 6822: Flows, Cuts, and Sparsifiers
Fall 2011.

CS 683: Learning, Games, and Electronic Markets
Spring 2007.

CS 783: Information-Theoretic Aspects of Algorithms
Fall 2007.

Curriculum Vitae

Research Interests

Algorithms and theoretical computer science, especially economic aspects of algorithms, online learning and its applications, random processes in networks.

Selected Recent Publications

• Universal Connection Schedules for Reconfigurable Networking
  S. Baral, R. Kleinberg, S. Martin, H. Rogers, T. Wilson, and R. Zhang.
  Proceedings of SODA 2026.
• Near-Optimal Algorithms for Omniprediction
  P. Okoroafor, R. Kleinberg, and M. P. Kim.
  Proceedings of FOCS 2025.
• Breaking the T^2/3 Barrier for Sequential Calibration
  Y. Dagan, C. Daskalakis, M. Fishelson, N. Golowich, R. Kleinberg, and P. Okoroafor.
  Proceedings of STOC 2025.
• Learning in Budgeted Auctions with Spacing Objectives
  G. Fikioris, R. Kleinberg, Y. Kolumbus, R. Kumar, Y. Mansour, and É Tardos.
  Proceedings of EC 2025.
• Distributed Load Balancing with Workload-Dependent Service Rates
  W. Zhang, S. R. Balseiro, R. Kleinberg, V. Mirrokni, B. Sivan, and B. Wydrowski.
  Proceedings of EC 2025.
• Shale: A Practical, Scalable Oblivious Reconfigurable Network
  D. Amir, N. Saran, T. Wilson, R. Kleinberg, V. Shrivastav, and H. Weatherspoon.
  Proceedings of SIGCOMM 2025.
• Breaking the VLB Barrier for Oblivious Reconfigurable Networks
  T. Wilson, D. Amir, N. Saran, R. Kleinberg, V. Shrivastav, and H. Weatherspoon.
  Proceedings of STOC 2024.
• Load is not what you should balance: Introducing Prequal
  B. Wydrowski, R. Kleinberg, S. Rumble, and A. Archer.
  Proceedings of NSDI 2024.
• Faster Recalibration of an Online Predictor via Approachability
  P. Okoroafor, R. Kleinberg, and W. Sun.
  Proceedings of AISTATS 2024.
• Online Convex Optimization with Unbounded Memory
  R. Kumar, S. Dean, and R. Kleinberg.
  Advances in Neural Information Processing Systems (NeurIPS 2023).
• U-Calibration: Forecasting for an Unknown Agent
  R. Kleinberg, R. Paes Leme, J. Schneider, and Y. Teng.
  Proceedings of COLT 2023.
• Non-Stochastic CDF Estimation Using Threshold Queries
  P. Okoroafor, V. Gupta, R. Kleinberg, and E. Goh.
  Proceedings of SODA 2023.
• Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem
  R. Kumar and R. Kleinberg.
  Advances in Neural Information Processing Systems (NeurIPS 2022).
• Individual Fairness in Prophet Inequalities
  M. Arsenis and R. Kleinberg.
  Proceedings of EC 2022.
• Optimal Oblivious Reconfigurable Networks
  D. Amir, T. Wilson, V. Shrivastav, H. Weatherspoon, R. Kleinberg, and R. Agarwal.
  Proceedings of STOC 2021.
• Recharging Bandits
  N. Immorlica and R. Kleinberg.
  Proceedings of FOCS 2018.
• Delegated Search Approximates Efficient Search
  J. Kleinberg and R. Kleinberg.
  Proceedings of EC 2018.
• The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
  J. Banks, R. Kleinberg, and C. Moore.
  SIAM J. Computing 48(3):1098–1119, 2019.
• The Growth Rate of Tri-Colored Sum-Free Sets
  R. Kleinberg, D. E. Speyer, and W. Sawin.
  Discrete Analysis 12, 2018.
• Semi-Oblivious Traffic Engineering: The Road Not Taken
  P. Kumar, Y. Yuan, C. Yu, N. Foster, R. Kleinberg, P. Lapukhov, C. L. Lim, and R. Soulé.
  Proc. 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2018).
• Tutorial on “Incentivizing and Coordinating Exploration” (EC 2017)
  Slides for Part I (Alex Slivkins), Part II (Bobby Kleinberg).
• Efficiency Through Procrastination: Approximately Optimal Algorithm Configuration with Runtime Guarantees
  R. Kleinberg, K. Leyton-Brown, and B. Lucier.
  In Proc. 26th International Joint Conference on Artificial Intelligence (IJCAI 2017).
• Bernoulli Factories and Black-Box Reductions in Mechanism Design
  S. Dughmi, J. Hartline, R. Kleinberg, and R. Niazadeh.
  In Proc. 49th ACM Symposium on Theory of Computing (STOC 2017).
• Descending Price Optimally Coordinates Search
  R. Kleinberg, B. Waggoner, and E. G. Weyl.
  In Proc. 17th ACM Conference on Economics and Computation (EC 2016).
• Incentivizing Exploration
  P. Frazier, D. Kempe, J. Kleinberg, and R. Kleinberg.
  Proc. 15th ACM Conference on Economics and Computation (EC 2014). (Recipient of Best Paper Award.)