Robert D. Kleinberg

Orcid: 0000-0002-8306-3407

Affiliations:
  • Cornell University, Ithaca, USA


According to our database1, Robert D. Kleinberg authored at least 162 papers between 2003 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2021, "For contributions to online learning and decision problems".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Load is not what you should balance: Introducing Prequal.
Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation, 2024

2023
Faster Recalibration of an Online Predictor via Approachability.
CoRR, 2023

Improving Oblivious Reconfigurable Networks with High Probability.
CoRR, 2023

U-Calibration: Forecasting for an Unknown Agent.
CoRR, 2023

Non-Stochastic CDF Estimation Using Threshold Queries.
CoRR, 2023

Non-Stochastic CDF Estimation Using Threshold Queries.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Poster: Scalability and Congestion Control in Oblivious Reconfigurable Networks.
Proceedings of the ACM SIGCOMM 2023 Conference, 2023

Online Convex Optimization with Unbounded Memory.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Extending Optimal Oblivious Reconfigurable Networks to all <i>N</i>.
Proceedings of the 2023 Symposium on Algorithmic Principles of Computer Systems, 2023

2022
A diameter-revealing proof of the Bondy-Lovász lemma.
Inf. Process. Lett., 2022

Optimal stopping with behaviorally biased agents: The role of loss aversion and changing reference points.
Games Econ. Behav., 2022

Optimal oblivious reconfigurable networks.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Individual Fairness in Prophet Inequalities.
Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022

Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem.
ACM Trans. Algorithms, 2021

Full surplus extraction from samples.
J. Econ. Theory, 2021

Bernoulli Factories and Black-box Reductions in Mechanism Design.
J. ACM, 2021

Threshold Tests as Quality Signals: Optimal Strategies, Equilibria, and Price of Anarchy.
Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Constrained-Order Prophet Inequalities.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Total Functions in the Polynomial Hierarchy.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020
Total Functions in the Polynomial Hierarchy.
Electron. Colloquium Comput. Complex., 2020

Revenue Monotonicity Under Misspecified Bidders.
Proceedings of the Web and Internet Economics - 16th International Conference, 2020

Online Flow Computation on Unit-Vertex-Capacitated Networks.
Proceedings of the 1st Symposium on Algorithmic Principles of Computer Systems, 2020

2019
Anonymous, Fault-Tolerant Distributed Queries for Smart Devices.
ACM Trans. Cyber Phys. Syst., 2019

The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime.
SIAM J. Comput., 2019

Bandits and Experts in Metric Spaces.
J. ACM, 2019

Matroid prophet inequalities and applications to multi-dimensional mechanism design.
Games Econ. Behav., 2019

Prior independent mechanisms via prophet inequalities with limited information.
Games Econ. Behav., 2019

Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Direct Uncertainty Prediction for Medical Second Opinions.
Proceedings of the 36th International Conference on Machine Learning, 2019

Pandora's Problem with Nonobligatory Inspection.
Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

2018
Merlin: A Language for Managing Network Resources.
IEEE/ACM Trans. Netw., 2018

Orienteering for electioneering.
Oper. Res. Lett., 2018

Bandits with Knapsacks.
J. ACM, 2018

Matroid Secretary Problems.
J. ACM, 2018

YATES: Rapid Prototyping for Traffic Engineering Systems.
Proceedings of the Symposium on SDN Research, 2018

Delegated Search Approximates Efficient Search.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Semi-Oblivious Traffic Engineering: The Road Not Taken.
Proceedings of the 15th USENIX Symposium on Networked Systems Design and Implementation, 2018

An Alternative View: When Does SGD Escape Local Minima?
Proceedings of the 35th International Conference on Machine Learning, 2018

Can Deep Reinforcement Learning solve Erdos-Selfridge-Spencer Games?
Proceedings of the 6th International Conference on Learning Representations, 2018

Recharging Bandits.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Semi-Oblivious Traffic Engineering with SMORE.
Proceedings of the Applied Networking Research Workshop, 2018

2017
Beating 1-1/e for ordered prophets.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Inferential Privacy Guarantees for Differentially Private Mechanisms.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Efficiency Through Procrastination: Approximately Optimal Algorithm Configuration with Runtime Guarantees.
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017

2016
Optimal Contest Design for Simple Agents.
ACM Trans. Economics and Comput., 2016

Kulfi: Robust Traffic Engineering Using Semi-Oblivious Routing.
CoRR, 2016

Descending Price Coordinates Approximately Efficient Search.
CoRR, 2016

Descending Price Optimally Coordinates Search.
Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Simultaneous Nearest Neighbor Search.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
Dynamic Pricing with Limited Supply.
ACM Trans. Economics and Comput., 2015

Building a Secure and Privacy-Preserving Smart Grid.
ACM SIGOPS Oper. Syst. Rev., 2015

Pricing lotteries.
J. Econ. Theory, 2015

Introduction to computer science and economic theory.
J. Econ. Theory, 2015

Truthful Mechanisms with Implicit Payment Computation.
J. ACM, 2015

Improving Christofides' Algorithm for the s-t Path TSP.
J. ACM, 2015

Bayesian incentive compatibility via matchings.
Games Econ. Behav., 2015

Approximately optimal auctions for correlated bidders.
Games Econ. Behav., 2015

Secretary Problems with Non-Uniform Arrival Order.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

On the Complexity of Computing an Equilibrium in Combinatorial Auctions.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Smooth Online Mechanisms: A Game-Theoretic Problem in Renewable Energy Markets.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Polymatroid Prophet Inequalities.
Proceedings of the Algorithms - ESA 2015, 2015

2014
A separability framework for analyzing community structure.
ACM Trans. Knowl. Discov. Data, 2014

Truthful germs are contagious: A local-to-global characterization of truthfulness.
Games Econ. Behav., 2014

Behavioral Mechanism Design: Optimal Contests for Simple Agents.
CoRR, 2014

Simple and Near-Optimal Mechanisms for Market Intermediation.
Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Prophet Inequalities with Limited Information.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Optimal auctions for correlated buyers with sampling.
Proceedings of the ACM Conference on Economics and Computation, 2014

Incentivizing exploration.
Proceedings of the ACM Conference on Economics and Computation, 2014

Combinatorial Partial Monitoring Game with Linear Feedback and Its Applications.
Proceedings of the 31th International Conference on Machine Learning, 2014

Merlin: A Language for Provisioning Network Resources.
Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, 2014

Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication.
Proceedings of the Approximation, 2014

2013
Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate.
IEEE Trans. Inf. Theory, 2013

Network Formation in the Presence of Contagious Risk.
ACM Trans. Economics and Comput., 2013

Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010).
SIAM J. Comput., 2013

A Unified Approach to Online Allocation Algorithms via Randomized Dual Fitting.
CoRR, 2013

Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

On the ratio of revenue to welfare in single-parameter mechanism design.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Multi-parameter mechanisms with implicit payment computation.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Trace complexity of network inference.
Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013

A Measure of Polarization on Social Media Networks Based on Community Boundaries.
Proceedings of the Seventh International Conference on Weblogs and Social Media, 2013

Managing the network with Merlin.
Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks, 2013

Optimal Stopping Meets Combinatorial Optimization.
Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

2012
The K-armed dueling bandits problem.
J. Comput. Syst. Sci., 2012

Matroid prophet inequalities.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

An analysis of one-dimensional schelling segregation.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Sketching valuation functions.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding.
Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

Learning on a budget: posted price mechanisms for online procurement.
Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

Optimal mechanisms for selling information.
Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

On the separability of structural classes of communities.
Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012

Approximating low-dimensional coverage problems.
Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

2011
Load balancing without regret in the bulletin board model.
Distributed Comput., 2011

Optimal auctions with correlated bidders are easy.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Beyond the Nash Equilibrium Barrier.
Proceedings of the Innovations in Computer Science, 2011

Which Networks are Least Susceptible to Cascading Failures?
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Lexicographic Products and the Power of Non-linear Network Coding.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Regret bounds for sleeping experts and bandits.
Mach. Learn., 2010

Truthfulness via Proxies
CoRR, 2010

Privacy-Compatibility For General Utility Metrics
CoRR, 2010

Index coding via linear programming
CoRR, 2010

Sharp Dichotomies for Regret Minimization in Metric Spaces.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Inapproximability for VCG-Based Combinatorial Auctions.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Pricing Randomized Allocations.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

The Serializability of Network Codes.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Improved Lower Bounds for the Universal and <i>a priori</i> TSP.
Proceedings of the Approximation, 2010

Nonmanipulable Randomized Tournament Selections.
Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010

2009
Foreword.
Theory Comput. Syst., 2009

Congestion games with malicious players.
Games Econ. Behav., 2009

Analyzing quadratic unconstrained binary optimization problems via multicommodity flows.
Discret. Appl. Math., 2009

Amplified Hardness of Approximation for VCG-Based Mechanisms
CoRR, 2009

Randomized Online Algorithms for the Buyback Problem.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Selling ad campaigns: online algorithms with cancellations.
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Online Bipartite Perfect Matching With Augmentations.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

Online Learning for Global Cost Functions.
Proceedings of the COLT 2009, 2009

2008
Online auctions and generalized secretary problems.
SIGecom Exch., 2008

Characterizing truthful mechanisms with convex type spaces.
SIGecom Exch., 2008

Hat Guessing Games.
SIAM J. Discret. Math., 2008

Competitive collaborative learning.
J. Comput. Syst. Sci., 2008

Online linear optimization and adaptive routing.
J. Comput. Syst. Sci., 2008

Multi-armed bandits in metric spaces.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

On the internet delay space dimensionality.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

Learning diverse rankings with multi-armed bandits.
Proceedings of the Machine Learning, 2008

2007
Oblivious routing on node-capacitated and directed graphs.
ACM Trans. Algorithms, 2007

Localized Client-Server Load Balancing without Global Information.
SIAM J. Comput., 2007

Emergence of tempered preferential attachment from optimization.
Proc. Natl. Acad. Sci. USA, 2007

Fast matrix multiplication is stable.
Numerische Mathematik, 2007

(Almost) Tight bounds and existence theorems for single-commodity confluent flows.
J. ACM, 2007

Fitting the WHOIS Internet data
CoRR, 2007

Noisy binary search and its applications.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Semi-oblivious routing: lower bounds.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Matroids, secretary problems, and online mechanisms.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Algorithmic pricing via virtual valuations.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

A "Chicken & Egg" Network Coding Problem.
Proceedings of the IEEE International Symposium on Information Theory, 2007

Geographic Routing Using Hyperbolic Space.
Proceedings of the INFOCOM 2007. 26th IEEE International Conference on Computer Communications, 2007

A Knapsack Secretary Problem with Applications.
Proceedings of the Approximation, 2007

Automated Online Mechanism Design and Prophet Inequalities.
Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007

2006
On the capacity of information networks.
IEEE Trans. Inf. Theory, 2006

Secretary Problems with Competing Employers.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Semi-oblivious routing.
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Anytime algorithms for multi-armed bandit problems.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

New lower bounds for oblivious routing in undirected graphs.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Improved lower and upper bounds for universal TSP in planar metrics.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

On the capacity of information networks.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005
Degree Distribution of Competition-Induced Preferential Attachment Graphs
CoRR, 2005

On the Competitive Ratio of the Random Sampling Auction.
Proceedings of the Internet and Network Economics, First International Workshop, 2005

Isomorphism and embedding problems for infinite limits of scale-free graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

A multiple-choice secretary algorithm with applications to online auctions.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Online client-server load balancing without global information.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Online auctions with re-usable goods.
Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005

Provably competitive adaptive routing.
Proceedings of the INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005

Group-theoretic Algorithms for Matrix Multiplication.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
A transport layer for live streaming in a content delivery network.
Proc. IEEE, 2004

(Almost) tight bounds and existence theorems for confluent flows.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Adaptive routing with end-to-end feedback: distributed learning and geometric approaches.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Adaptive limited-supply online auctions.
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Nearly Tight Bounds for the Continuum-Armed Bandit Problem.
Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004

Competition-Induced Preferential Attachment.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
Consistent load balancing via spread minimization.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003


  Loading...