Robert D. Kleinberg

Associate 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 6820: Analysis of Algorithms
        Fall 2008, Fall 2010, Fall 2012.

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.

Research Interests

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

Recent Publications

• Bandits with Knapsacks
  A. Badanidiyuru, R. Kleinberg, and A. Slivkins.
  Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), to appear.
• Trace Complexity of Network Inference
  B. Abrahao, F. Chierichetti, R. Kleinberg, and A. Panconesi.
  Proceedings of the 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2013), to appear.
• On the Ratio of Revenue to Welfare in Single-Parameter Mechanism Design
  R. Kleinberg and Y. Yuan.
  Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013).
• Multi-parameter Mechanisms with Implicit Payment Computation
  M. Babaioff, R. Kleinberg, and A. Slivkins.
  Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013).
• Broadcasting with Side Information: Bounding and Approximating the Broadcast Rate
  A. Blasiak, R. Kleinberg, and E. Lubetzky.
  IEEE Transactions on Information Theory, to appear.
• A Measure of Polarization on Social Media Networks Based on Community Boundaries
  P. H. Calais Guerra, W. Meira, Jr., C. Cardie, and R. Kleinberg.
  Proceedings of the 7th AAAI Conference on Weblogs and Social Media (ICWSM 2013).
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
  N. R. Devanur, K. Jain, and R. Kleinberg.
  Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013).
• On the Separability of Structural Classes of Communities
  B. Abrahao, S. Soundarajan, J. Hopcroft, and R. Kleinberg.
  Proc. 18th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2012).
• Optimal Mechanisms for Selling Information
  M. Babaioff, R. Kleinberg, and R. Paes Leme.
  Proc. 13th Annual ACM Conference on Electronic Commerce (EC 2012).
• Conditional Equilibria Via Ascending Price Processes with Applications to Combinatorial Auctions with Item Bidding
  H. Fu, R. Kleinberg, and R. Lavi.
  Proc. 13th Annual ACM Conference on Electronic Commerce (EC 2012).
• Learning on a Budget: Posted Price Mechanisms for Online Procurement
  A. Badanidiyuru, R. Kleinberg, and Y. Singer.
  Proc. 13th Annual ACM Conference on Electronic Commerce (EC 2012).
• Dynamic Pricing with Limited Supply.
  M. Babaioff, S. Dughmi, R. Kleinberg, and A. Slivkins.
  Proc. 13th Annual ACM Conference on Electronic Commerce (EC 2012).
• An Analysis of of One-Dimensional Schelling Segregation
  C. Brandt, N. Immorlica, G. Kamath, and R. Kleinberg.
  Proc. 44th Annual ACM Symposium on Theory of Computing (STOC 2012).
• Matroid Prophet Inequalities
  R. Kleinberg and S. M. Weinberg.
  Proc. 44th Annual ACM Symposium on Theory of Computing (STOC 2012).
• Improving Christofides' Algorithm for the s-t Path TSP
  H.-C. An, R. Kleinberg, and D. B. Shmoys.
  Proc. 44th Annual ACM Symposium on Theory of Computing (STOC 2012).

Full Chronological List of Publications