Robert David Kleinberg
Professor
Computer Science DEPT · BCIS
274 publications
11,222 citations
54 h-index
Decision Sciences
Recent Papers (40)
2026-03-04 · ArXiv.org · Management Science and Operations Research
Oracle-efficient Hybrid Learning with Constrained Adversaries
Robert KleinbergProfessor, Computer Science DEPT · BCIS
Michael P. KimProf Asst, Computer Science DEPT · BCIS
2026-01-01 · Society for Industrial and Applied Mathematics eBooks · Computer Networks and Communications
The \(k\)-Fold Matroid Secretary Problem
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2026-01-01 · Society for Industrial and Applied Mathematics eBooks · Computer Networks and Communications
Universal Connection Schedules for Reconfigurable Networking
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2025-12-14 · Management Science and Operations Research
Near-Optimal Algorithms for Omniprediction
Robert KleinbergProfessor, Computer Science DEPT · BCIS
Michael P. KimProf Asst, Computer Science DEPT · BCIS
2022-01-01
Threshold Tests as Quality Signals: Optimal Strategies, Equilibria, and Price of Anarchy
Siddhartha BanerjeeProf Assoc, Operations Research & Info Eng DEPT · EN
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2021-08-20
A diameter-revealing proof of the Bondy-Lovász lemma
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2021-01-06
Bernoulli Factories and Black-box Reductions in Mechanism Design
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2021-01-01
Constrained-Order Prophet Inequalities
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2020-12-28
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
Robert KleinbergProfessor, Computer Science DEPT · BCIS
David B. ShmoysProfessor, Operations Research & Info Eng DEPT · EN
2020-01-01
Revenue Monotonicity Under Misspecified Bidders
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2019-05-31
Bandits and Experts in Metric Spaces
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2019-05-04
Pandora's Problem with Nonobligatory Inspection
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2019-02-14
Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2018-07-04
Direct Uncertainty Prediction for Medical Second Opinions
Robert KleinbergProfessor, Computer Science DEPT · BCIS
Jon KleinbergProfessor, Computer Science DEPT · BCIS
2018-06-18
Delegated Search Approximates Efficient Search
Jon KleinbergProfessor, Computer Science DEPT · BCIS
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2018-02-17
An Alternative View: When Does SGD Escape Local Minima?
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2017-11-07
Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?
Robert KleinbergProfessor, Computer Science DEPT · BCIS
Jon KleinbergProfessor, Computer Science DEPT · BCIS
2017-06-15
Beating 1-1/e for ordered prophets
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2016-07-21
Descending Price Optimally Coordinates Search
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2016-03-04
Inferential Privacy Guarantees for Differentially Private Mechanisms
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2015-03-27
Dynamic Pricing with Limited Supply
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2015-02-07
Secretary Problems with Non-Uniform Arrival Order
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2014-09-09
Simple and Near-Optimal Mechanisms For Market Intermediation
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2014-07-04
Merlin: A Language for Provisioning Network Resources
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2014-06-06
Optimal Auctions for Correlated Buyers with Sampling
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2013-10-01
Bandits with Knapsacks
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2013-08-13
Trace Complexity of Network Inference
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2013-08-07
Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2012-04-25
Optimal Mechanisms for Selling Information
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2012-03-28
An Analysis of One-Dimensional Schelling Segregation
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2011-12-03
Approximating Low-Dimensional Coverage Problems
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2011-10-20
Improving Christofides' Algorithm for the s-t Path TSP
Robert KleinbergProfessor, Computer Science DEPT · BCIS
David B. ShmoysProfessor, Operations Research & Info Eng DEPT · EN
2011-08-11
Lexicographic products and the power of non-linear network coding
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2011-01-03
Continuous-time model of structural balance
Jon KleinbergProfessor, Computer Science DEPT · BCIS
Robert KleinbergProfessor, Computer Science DEPT · BCIS
Steven H. StrogatzProfessor, Mathematics · CAS
2010-11-10
Optimal Auctions with Correlated Bidders are Easy
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2010-04-21
Truthful Mechanisms with Implicit Payment Computation
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2010-01-08
The Serializability of Network Codes
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2008-09-29
Multi-Armed Bandits in Metric Spaces
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2008-08-12
Algorithmic Pricing via Virtual Valuations
Robert KleinbergProfessor, Computer Science DEPT · BCIS
2005-11-15
Group-theoretic Algorithms for Matrix Multiplication
Robert KleinbergProfessor, Computer Science DEPT · BCIS