Robert D. Kleinberg

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Anonymous, Fault-Tolerant Distributed Queries for Smart Devices.
TCPS, 2019

Matroid prophet inequalities and applications to multi-dimensional mechanism design.
Games and Economic Behavior, 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

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

Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?
Proceedings of the 35th International Conference on Machine Learning, 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
Bernoulli factories and black-box reductions in mechanism design.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 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

The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime.
Proceedings of the Approximation, 2017

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
Building a Secure and Privacy-Preserving Smart Grid.
Operating Systems Review, 2015

Pricing lotteries.
J. Economic Theory, 2015

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

Approximately optimal auctions for correlated bidders.
Games and Economic Behavior, 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.
TKDD, 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 contest design for simple agents.
Proceedings of the ACM Conference on Economics and Computation, 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. Information Theory, 2013

Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010).
SIAM J. Comput., 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

Bandits with Knapsacks.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

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

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

Improving christofides' algorithm for the s-t path TSP.
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

Dynamic pricing with limited supply.
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 Symposuim on Computational Geometry 2012, 2012

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

Bayesian Incentive Compatibility via Matchings.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Network formation in the presence of contagious risk.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 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
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

Truthful mechanisms with implicit payment computation.
Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010

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

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

Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem.
Proceedings of the Approximation, 2010

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

2009
Hat Guessing Games.
SIAM Review, 2009

Foreword.
Theory Comput. Syst., 2009

Analyzing quadratic unconstrained binary optimization problems via multicommodity flows.
Discrete Applied Mathematics, 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

Load balancing without regret in the bulletin board model.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

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

The K-armed Dueling Bandits Problem.
Proceedings of the COLT 2009, 2009

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

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

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

Hat Guessing Games.
SIAM J. Discrete Math., 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

Truthful germs are contagious: a local to global characterization of truthfulness.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

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

On the internet delay space dimensionality.
Proceedings of the 8th ACM SIGCOMM Internet Measurement Conference, 2008

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

Regret Bounds for Sleeping Experts and Bandits.
Proceedings of the 21st Annual Conference on Learning Theory, 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

Fast matrix multiplication is stable.
Numerische Mathematik, 2007

(Almost) Tight bounds and existence theorems for single-commodity confluent flows.
J. ACM, 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

Congestion games with malicious players.
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. Information 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
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

Oblivious routing on node-capacitated and directed graphs.
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

Competitive Collaborative Learning.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

2004
A transport layer for live streaming in a content delivery network.
Proceedings of the 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...