Research

I am interested in problems at the intersection of game theory and algorithms.  Much of my recent work has been motivated by Internet applications, particularly the design of ad auctions for search engines such as Google's AdWords, Yahoo! SearchMarketing, or MSN's AdCenter.  I have also worked on approximation algorithms for problems in network design and clustering.

Publications

  1. M. Babaioff, M. Dinitz, A. Gupta, N. Immorlica, and K. Talwar. Secretary Problems: Weights and Discounts, SODA 2009.
  2. M. Babaioff, N. Immorlica, D. Kempe, and R.D. Kleinberg. Online Auctions and Generalized Secretary Problems, SIGecom Exchanges 7(2), June 2008.
  3. C. Borgs, J. Chayes, N. Immorlica, A. Kalai, V. Mirrokni, and C. Papadimitriou. The Myth of the Folk Theorem, STOC 2008.
  4. U. Feige, N. Immorlica, V. Mirrokni, and H. Nazerzadeh. A Combinatorial Allocation Mechanism for Banner Advertisement with Penalties, WWW 2008.
  5. N. Immorlica, A. Karlin, M. Mahdian, and K. Talwar. Balloon popping with applications to ascending auctions, FOCS 2007.
  6. M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg.A Knapsack Secretary Problem with Applications, APPROX 2007.
  7. N. Immorlica, J. Kleinberg, M. Mahdian, and T. Wexler. The role of compatibility in the diffusion of technologies in social networks, EC 2007.
  8. C. Borgs, J. Chayes, O. Etesami, N. Immorlica, K. Jain, and M. Mahdian. Dynamics of bid optimization in online advertisement auctions, WWW 2007.
  9. M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, Secretary Problems, and Online Mechanisms, SODA 2007.
  10. N. Immorlica, K. Jain, and M. Mahdian. Game-Theoretic Aspects of Designing Hyperlink Structures, Workshop on Internet and Network Economics (WINE), 2006.
  11. N. Immorlica, R. Kleinberg, and M. Mahdian. Secretary Problems with Competing Employers, Workshop on Internet and Network Economics (WINE), 2006.
  12. B. Dean, M. Goemans, and N. Immorlica. Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data, European Symposium on Algorithms (ESA), 2006.
  13. B. Dean, M. Goemans, and N. Immorlica. The Unsplittable Stable Marriage Problem, IFIP International Conference on Theoretical Computer Science (IFIP TCS), 2006.
  14. N. Immorlica, L. Li, V. Mirrokni, and A. Schulz. Coordination Mechanisms for Selfish Scheduling, Workshop on Internet and Network Economics (WINE), 2005.
  15. N. Immorlica, K. Jain, M. Mahdian, and K. Talwar. Click Fraud Resistant Methods for Learning Click-Through Rates, Workshop on Internet and Network Economics (WINE), 2005.
  16. G. Aggarwal, A. Fiat, A. Goldberg, J. Hartline, N. Immorlica, and M. Sudan. Derandomization of Auctions, STOC 2005.
  17. N. Immorlica, D. Karger, E. Nikolova, and R. Sami. First-Price Path Auctions, EC 2005.
  18. C. Borgs, J. Chayes, N. Immorlica, M. Mahdian, and A. Saberi. Multi-Unit Auctions with Budget-Constrained Bidders, EC 2005.
  19. N. Immorlica and M. Mahdian. Marriage, Honesty, and Stability, SODA 2005.
  20. N. Immorlica, M. Mahdian, and V. Mirrokni. Limitations of cross-monotonic cost-sharing schemes, ACM Transactions on Algorithms special issue, volume 4, number 2, April 2008. Conference version appeared in SODA 2005 and was winner of the best student paper award.
  21. N. Immorlica and S. Chien. Semantic Similarity between Search Engine Queries Using Temporal Correlation, WWW 2005.
  22. R. Bhatia, N. Immorlica, T. Kimbrel, V.S. Mirrokni, S. Naor, B. Schieber. Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees, Theory of Computing Systems, volume 41, number 1, January 2008, pages 2-26.  Conference version appeared in SPAA 2005.
  23. N. Immorlica, M. Mahdian, and V. Mirrokni. Cycle cover with short cycles, STACS 2005.
  24. N. Immorlica, D. Karger, M. Minkoff, and V. Mirrokni. On the Costs and Benefits of Procrastination: Approximation Algorithms for Stochastic Combinatorial Optimization Problems, SODA 2004.
  25. M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions, SoCG 2004.
  26. E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation Clustering in General Weighted Graphs, Theoretical Computer Science special issue, volume 361, number 2-3, September 2006, pages 172-187.  Conference version (E.D. Demaine and N. Immorlica, Correlation Clustering with Partial Information) appeared in APPROX 2003.
  27. Y. Bejarano, N. Immorlica, S. Noar, and M. Smith. Location Area Design in Cellular Networks, MOBICOM 2003. Full version: Efficient Location Area Planning for Personal Communication Systems, IEEE/ACM Transactions on Networking, volume 14, number 2, April 2006, pages 438-450.
  28. M. Hajiaghayi, N. Immorlica, and V. Mirrokni. Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks, to appear in IEEE/ACM Transactions on Networking.  Conference version appeared in MOBICOM 2003.

Thesis

  1. Ph.D. Thesis, Computing With Strategic Agents
  2. Masters Thesis, Data Acquisition System Design for the Alpha Magnetic Spectrometer

Papers in Preparation

  1. N. Chen, N. Immorlica, A. Karlin, M. Mahdian, and A. Rudra. Approximating Matches Made in Heaven, in preparation, 2008.
  2. U. Feige, N. Immorlica, V. Mirrokni, and H. Nazerzadeh. Functional Approximations: A New Framework for Analyzing Heuristics, in preparation, 2008.
  3. R. DePrisco, N. Lynch, A. Shvartsman, N. Immorlica, and T. Ne Win. A Formal Treatment of Lamport's Paxos Algorithm, (permanently) in preparation.