Robert Kleinberg's Publications

• Multiplicative updates outperform generic no-regret learning in congestion games
  R. Kleinberg, G. Piliouras, and E. Tardos.
  To appear in Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS 2008).
  Paper is in preparation. Link coming soon.

  Selling banner ads: Online algorithms with buyback

  M. Babaioff, J. D. Hartline, and R. Kleinberg.

  Workshop on Ad Auctions 2008, Chicago, Illinois, USA.

  Brief announcement: On the Internet delay space dimensionality

  B. Abrahao and R. Kleinberg.

  To appear in Proceedings of the 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2008).

  Truthful germs are contagious: A local-to-global characterization of truthfulness

  A. Archer and R. Kleinberg.

  To appear in Proceedings of the 9th ACM Conference on Electronic Commerce (EC 2008).

  Learning diverse rankings with multi-armed bandits

  F. Radlinski, R. Kleinberg, and T. Joachims.

  To appear in Proceedings of the 25th International Conference on Machine Learning (ICML 2008).

  Regret bounds for sleeping experts and bandits

  R. Kleinberg, A. Niculescu-Mizil, and Y. Sharma.

  To appear in Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008).

  Multi-armed bandit problems in metric spaces

  R. Kleinberg, A. Slivkins, and E. Upfal.

  In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC 2008), pp. 681-690.

  Automated online mechanism design and prophet inequalities

  M. Hajiaghayi, R. Kleinberg, and T. Sandholm.

  In Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07), pp. 58-65.

  A "chicken and egg" network coding problem

  N. Harvey, R. Kleinberg, C. Nair, and Y. Wu.

  In Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT 2007).

  Congestion games with malicious players

  M. Babaioff, R. Kleinberg, and C. Papadimitriou.

  In Proceedings of the 8th ACM Conference on Electronic Commerce (EC 2007), pp. 103-112.

  Algorithmic pricing via virtual valuations

  S. Chawla, J. Hartline, and R. Kleinberg.

  In Proceedings of the 8th ACM Conference on Electronic Commerce (EC 2007), pp. 243-251.

  Emergence of tempered preferential attachment from optimization

  R. M. D'Souza, C. Borgs, J. T. Chayes, N. Berger, and R. Kleinberg.

  Proceedings of the National Academy of Sciences (PNAS), 104 (15): 6112-6117, 2007.

  Geographic routing using hyperbolic space

  Robert Kleinberg.

  In Proceedings of the 26th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2007), pp. 1902-1909.

  Fast matrix multiplication is stable

  James Demmel, Ioana Dumitriu, Olga Holtz, and Robert Kleinberg.

  Numerische Mathematik 106(2):199-224, 2007.

  Matroids, secretary problems, and online mechanisms

  Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg.

  In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 434-443.

  Semi-oblivious routing: lower bounds

  MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tom Leighton.

  In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 929-938.

  Noisy binary search and its applications

  Richard Karp and Robert Kleinberg.

  In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 881-890.

  Secretary problems with competing employers

  Nicole Immorlica, Robert Kleinberg, and Mohammad Mahdian.

  In Proceedings of the 2nd Workshop on Internet and Network Economics (WINE 2006), pp. 389-400.

  Hat guessing games

  Steven Butler, MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tom Leighton.

  To appear in SIAM Journal on Discrete Mathematics.

  On the capacity of information networks

  Nicholas Harvey, Robert Kleinberg, and April Rasala Lehman.

  Special Issue of the IEEE Transactions on Information Theory and the IEEE/ACM Transactions on Networking, 52(6):2345-2364, June 2006.

  Anytime algorithms for multi-armed bandit problems

  Robert Kleinberg.

  In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 928-936.

  Improved lower and upper bounds for universal TSP in planar metrics

  Mohammad Hajiaghayi, Robert Kleinberg, and Tom Leighton.

  In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 649-658.

  New lower bounds for oblivious routing in undirected graphs

  Mohammad Hajiaghayi, Robert Kleinberg, Tom Leighton, and Harald Racke.

  In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 918-927.

  On the capacity of information networks

  Micah Adler, Nicholas Harvey, Kamal Jain, Robert Kleinberg, and April Rasala Lehman.

  In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 241-250.

  On the competitive ratio of the random sampling auction

  Uriel Feige, Abraham Flaxman, Jason Hartline, and Robert Kleinberg.

  In Proceedings of the 1st Workshop on Internet and Network Economics (WINE 2005), pp. 878-886.

  Group-theoretic algorithms for matrix multiplication

  Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans.

  In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 379-388.

  Tighter cut-based bounds for k-pairs communication problems

  Nicholas Harvey and Robert Kleinberg.

  Invited Paper, 43rd Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, September 2005.

  Competitive collaborative learning

  Baruch Awerbuch and Robert Kleinberg.

  To appear in Journal of Computer and System Sciences, special issue on computational learning theory.

  Extended abstract appeared in Proceedings of the 18th Annual Conference on Learning Theory (COLT 2005), pp. 233-248.

  Online auctions with re-usable goods

  Mohammad Hajiaghayi, Robert Kleinberg, Mohammad Mahdian, and David Parkes.

  In Proceedings of the 6th ACM Conference on Electronic Commerce (EC 2005), pages 165--174.

  A multiple-choice secretary problem with applications to online auctions

  Robert Kleinberg.

  In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 630-631.

  Localized client-server load balancing without global information

  Baruch Awerbuch, Mohammad Hajiaghayi, Robert Kleinberg, and Tom Leighton.

  SIAM Journal on Computing, 37(4):1259-1279.

  Extended abstract appeared in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 197-206.

  Oblivious routing on node-capacitated and directed graphs

  Mohammad Hajiaghayi, Robert Kleinberg, Tom Leighton, and Harald Racke.

  ACM Transactions on Algorithms (TALG) 3 (4), November 2007.

  Extended abstract appeared in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 782-790.

  Isomorphism and embedding problems for infinite limits of scale-free graphs

  Robert Kleinberg and Jon Kleinberg.

  In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 277-286.

  Provably competitive adaptive routing

  Baruch Awerbuch, David Holmer, Herbert Rubens, and Robert Kleinberg.

  In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005), pp. 631-641.

  Nearly tight bounds for the continuum-armed bandit problem

  Robert Kleinberg.

  In Advances in Neural Information Processing Systems 17 (NIPS 2004), pp. 697-704.

  Degree distribution of competition-induced preferential attachment graphs

  Noam Berger, Christian Borgs, Jennifer Chayes, Raissa D'Souza, and Robert Kleinberg.

  Combinatorics, Probability, and Computing 14 (5-6): 697-721.

  Extended abstract appeared in Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004), pages 208-221.

  A transport layer for live streaming in a content delivery network

  Leonidas Kontothanassis, Ramesh Sitaraman, Joel Wein, Duke Hong, Robert Kleinberg, Brian Mancuso, David Shaw, and Daniel Stodolsky.

  Proceedings of the IEEE, Special Issue on Evolution of Internet Technologies 92(9):1408-1419 (September, 2004).

  (Almost) tight bounds and existence theorems for single-commodity confluent flows

  Jiangzhuo Chen, Robert Kleinberg, Laszlo Lovasz, Rajmohan Rajaraman, Ravi Sundaram, and Adrian Vetta.

  Journal of the ACM, 54 (4), July 2007.

  Extended abstract appeared in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), pages 529-538.

  Online linear optimization and adaptive routing

  Baruch Awerbuch and Robert Kleinberg.

  Journal of Computer and System Sciences, 74(1):97-114. Special issue on computational learning theory, February 2008.

  Extended abstract appeared in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), pages 45-53.

  Adaptive limited-supply online auctions

  Mohammad Hajiaghayi, Robert Kleinberg, and David Parkes.

  In Proceedings of the 5th ACM Conference on Electronic Commerce (EC 2004), pages 71-80.

  The value of knowing a demand curve: bounds on regret for on-line posted-price auctions

  Robert Kleinberg and Tom Leighton.

  In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS 2003), pages 594-605.

  Consistent load balancing via spread minimization

  Robert Kleinberg and Tom Leighton.

  In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC 2003), pages 565-574.

  Online decision problems with large strategy sets

  Robert Kleinberg.

  Ph.D. Thesis, MIT, 2005.