Robert D. Kleinberg

Professor of Computer Science, Cornell University

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

Ph.D. Students

        Former Students

Postdocs

Former Postdocs

Teaching

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   

• 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.)