Vahab Mirrokni

Vahab Mirrokni is a Senior Research Scientist at Google. He has joined Google Research in New York in 2008, after a couple of years as a researcher at Microsoft Research, MIT and Amazon.com. He received his PhD from MIT in 2005 and his B.Sc. from Sharif University of Technology in 1999. He is the co-winner of a SODA05 best student paper award and ACM EC08 best paper award. His research areas include algorithms, algorithmic game theory, combinatorial optimization, and social networks analysis. At Google, he is mainly working on algorithmic and economic problems related to search and online advertising. He also has a personal homepage.

Publications

• “Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation”, Vahab Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam, Symposium on Discrete Algorithms (SODA) 2012 (to appear).
  [search]

• “Inner Product Spaces for MinSum Coordination Mechanisms”, Richard Cole, Jose R. Correa, Vasilis Gkatzelis, Vahab Mirrokni, Neil Olver, STOC, 2011.
  [arxiv.org] [search]

• “Large-scale community detection on YouTube for Topic Discovery and Exploration”, Ullas Gargi, Wenjun Lu, Vahab Mirrokni, Sangho Yoon, AAAI Conference on Weblogs and Social Media 2011.
  [pdf] [search]

• “Online Stochastic Weighted Matching: Improved Approximation Algorithms”, Bernard Haeupler, Vahab Mirrokni, Morteza Zadimoghaddam, Workshop of Network and Internet Economics (WINE) 2011 (to appear).
  [search]

• “Optimal Auctions with Positive Network Externalities”, Nima Haghpanah, Nicole Immorlica, Vahab Mirrokni, K. Munagala, ACM Conference on Electronic Commerce, 2011.
  [search]

• “Yield Optimization of Display Advertising with Ad Exchange”, Santiago Balseiro, Jon Feldman, Vahab Mirrokni, S. Muthukrishnan, ACM Conference on Electronic Commerce, 2011.
  [abstract] [arxiv.org] [search]

• “Auctions with intermediaries: extended abstract”, Jon Feldman, Vahab S. Mirrokni, S. Muthukrishnan, Mallesh M. Pai, ACM Conference on Electronic Commerce, 2010, pp. 23-32.
  [doi.acm.org] [search]

• “Equilibrium Pricing with Positive Externalities (Extended Abstract)”, Nima Anari, Shayan Ehsani, Mohammad Ghodsi, Nima Haghpanah, Nicole Immorlica, Hamid Mahini, Vahab Mirrokni, WINE, 2010, pp. 424-431.
  [doi] [search]

• “Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints”, Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko, SIAM J. Discrete Math., vol. 23 (2010), pp. 2053-2078.
  [doi] [search]

• “Mining advertiser-specific user behavior using adfactors”, Nikolay Archak, Vahab S. Mirrokni, S. Muthukrishnan, WWW, 2010, pp. 31-40.
  [doi.acm.org] [search]

• “Online Stochastic Packing Applied to Display Ad Allocation”, Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, Clifford Stein, ESA (1), 2010, pp. 182-194.
  [doi] [search]

• “Optimal Iterative Pricing over Social Networks (Extended Abstract)”, Hessameddin Akhlaghpour, Mohammad Ghodsi, Nima Haghpanah, Vahab Mirrokni, Hamid Mahini, Afshin Nikzad, WINE, 2010, pp. 415-423.
  [doi] [search]

• “Optimal marketing and pricing over social networks”, Nicole Immorlica, Vahab S. Mirrokni, WWW, 2010, pp. 1349-1350.
  [doi.acm.org] [search]

• “Quasi-Proportional Mechanisms: Prior-free Revenue Maximization”, Vahab S. Mirrokni, S. Muthukrishnan, Uri Nadav, Latin, 2010, to appear.
  [search]

• “Approximating Submodular Functions Everywhere”, Michel Goemans, Nick Harvey, S. Iwata, Vahab Mirrokni, Symposium on Discrete Algorithms (SODA), 2009.
  [search]

• “Bid optimization for broad match ad auctions”, Eyal Even-Dar, Vahab S. Mirrokni, S. Muthukrishnan, Yishay Mansour, Uri Nadav, WWW, 2009, pp. 231-240.
  [doi.acm.org] [search]

• “Competitive Routing over Time”, Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, Shang-Hua Teng, Workshop of Internet Economics (WINE), 2009, pp. 18-29.
  [doi] [search]

• “Coordination mechanisms for selfish scheduling”, Nicole Immorlica, Li (Erran) Li, Vahab S. Mirrokni, Andreas S. Schulz, Theor. Comput. Sci., vol. 410 (2009), pp. 1589-1598.
  [doi] [search]

• “Non-monotone submodular maximization under matroid and knapsack”, Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko, STOC, 2009, pp. 323-332.
  [doi.acm.org] [search]

• “On the complexity of nash dynamics and sink equilibria”, Vahab S. Mirrokni, Alexander Skopalik, ACM Conference on Electronic Commerce, 2009, pp. 1-10.
  [doi.acm.org] [search]

• “Online Ad Assignment with Free Disposal”, Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, Martin Pál, Workshop of Internet Economics (WINE), 2009, pp. 374-385.
  [doi] [search]

• “Online Stochastic Matching: Beating 1-1/e”, Jon Feldman, Aranyak Mehta, Vahab Mirrokni, S. Muthukrishnan, Symposium on the Foundations of Computer Science (FOCS), 2009.
  [arxiv.org] [search]

• “PASS Approximation”, Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh, APPROX-RANDOM, 2009, pp. 111-124.
  [doi] [search]

• “Tutorial summary: Convergence of natural dynamics to equilibria”, Eyal Even-Dar, Vahab S. Mirrokni, ICML, 2009, pp. 173.
  [doi.acm.org] [search]

• “Permutation betting markets: singleton betting with extra information”, Mohammad Ghodsi, Hamid Mahini, Vahab S. Mirrokni, Morteza Zadimoghaddam, ACM Conference on Electronic Commerce, 2008, pp. 180-189.
  [doi.acm.org] [search]

• “Two-Stage Robust Network Design with Exponential Scenarios”, Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour, ESA, 2008, pp. 589-600.
  [doi] [search]

Prior Publications

• “Secure Overlay Network Design”, Li (Erran) Li, Mohammad Mahdian, Vahab S. Mirrokni, Algorithmica, vol. 57 (2010), pp. 82-96.
  [doi] [search]

• “(Almost) optimal coordination mechanisms for unrelated machine scheduling”, Yossi Azar, Kamal Jain, Vahab S. Mirrokni, SODA, 2008, pp. 323-332.
  [doi.acm.org] [search]

• “A combinatorial allocation mechanism with penalties for banner advertising”, Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh, WWW, 2008, pp. 169-178.
  [doi.acm.org] [search]

• “Approximating Minimum-Power Degree and Connectivity Problems”, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko, LATIN, 2008, pp. 423-435.
  [doi] [search]

• “Fast convergence to nearly optimal solutions in potential games”, Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab S. Mirrokni, Alexander Skopalik, ACM Conference on Electronic Commerce, 2008, pp. 264-273.
  [doi.acm.org] [search]

• “Limitations of cross-monotonic cost-sharing schemes”, Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni, ACM Transactions on Algorithms, vol. 4 (2008).
  [doi.acm.org] [search]

• “Market Games and Content Distribution”, Vahab S. Mirrokni, Encyclopedia of Algorithms, 2008.
  [doi] [search]

• “On the Stability of Web Crawling and Web Search”, Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Vahab S. Mirrokni, Shang-Hua Teng, ISAAC, 2008, pp. 680-691.
  [doi] [search]

• “Optimal marketing strategies over social networks”, Jason D. Hartline, Vahab S. Mirrokni, Mukund Sundararajan, WWW, 2008, pp. 189-198.
  [doi.acm.org] [search]

• “Robust PageRank and locally computable spam detection features”, Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Kamal Jain, Vahab S. Mirrokni, Shang-Hua Teng, AIRWeb, 2008, pp. 69-76.
  [doi.acm.org] [search]

• “The myth of the folk theorem”, Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou, STOC, 2008, pp. 365-372.
  [doi.acm.org] [search]

• “Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions”, Vahab S. Mirrokni, Michael Schapira, Jan Vondr\'ak, ACM Conference on Electronic Commerce, 2008, pp. 70-77.
  [doi.acm.org] [search]

• “Trust-based recommendation systems: an axiomatic approach”, Reid Andersen, Christian Borgs, Jennifer T. Chayes, Uriel Feige, Abraham D. Flaxman, Adam Kalai, Vahab S. Mirrokni, Moshe Tennenholtz, WWW, 2008, pp. 199-208.
  [doi.acm.org] [search]

• “Uncoordinated two-sided matching markets”, Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko R\, Berthold V\, ACM Conference on Electronic Commerce, 2008, pp. 256-263.
  [doi.acm.org] [search]

• “A Unified Approach to Congestion Games and Two-Sided Markets”, Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko R\, Berthold V\, WINE, 2007, pp. 30-41.
  [doi] [search]

• “Cell Breathing in Wireless LANs: Algorithms and Evaluation”, Paramvir Bahl, Mohammad Taghi Hajiaghayi, Kamal Jain, Vahab S. Mirrokni, Lili Qiu, Amin Saberi, IEEE Trans. Mob. Comput., vol. 6 (2007), pp. 164-178.
  [doi.ieeecomputersociety.org] [search]

• “Local Computation of PageRank Contributions”, Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcraft, Vahab S. Mirrokni, Shang-Hua Teng, WAW, 2007, pp. 150-165.
  [doi] [search]

• “Maximizing Non-Monotone Submodular Functions”, Uriel Feige, Vahab S. Mirrokni, Jan Vondr\'ak, FOCS, 2007, pp. 461-471.
  [doi.ieeecomputersociety.org] [search]

• “Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks”, Mohammad Taghi Hajiaghayi, Nicole Immorlica, Vahab S. Mirrokni, IEEE/ACM Trans. Netw., vol. 15 (2007), pp. 1345-1358.
  [doi.acm.org] [search]

• “Robust Combinatorial Optimization with Exponential Scenarios”, Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab S. Mirrokni, IPCO, 2007, pp. 439-453.
  [doi] [search]

• “Subjective-cost policy routing”, Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, Rahul Sami, Theor. Comput. Sci., vol. 378 (2007), pp. 175-189.
  [doi] [search]

• “A relation between choosability and uniquely list colorability”, Saieed Akbari, Vahab S. Mirrokni, Bashir S. Sadjad, J. Comb. Theory, Ser. B, vol. 96 (2006), pp. 577-583.
  [doi] [search]

• “Assignment Problems in Rental Markets”, David Abraham, Ning Chen, Vijay Kumar, Vahab S. Mirrokni, WINE, 2006, pp. 198-213.
  [doi] [search]

• “Bandwidth Sharing Network Design for Multi-Class Traffic”, Mohammad Taghi Hajiaghayi, Li Li, Vahab S. Mirrokni, Marina Thottan, INFOCOM, 2006.
  [doi] [search]

• “Convergence and Approximation in Potential Games”, George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos, STACS, 2006, pp. 349-360.
  [doi] [search]

• “Fault-Tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks”, Mohsen Bahramgiri, Mohammad Taghi Hajiaghayi, Vahab S. Mirrokni, Wireless Networks, vol. 12 (2006), pp. 179-188.
  [doi] [search]

• “Market sharing games applied to content distribution in ad hoc networks”, Michel X. Goemans, Li Li, Vahab S. Mirrokni, Marina Thottan, IEEE Journal on Selected Areas in Communications, vol. 24 (2006), pp. 1020-1033.
  [doi.ieeecomputersociety.org] [search]

• “Secure Overlay Network Design”, Erran L. Li, Mohammad Mahdian, Vahab S. Mirrokni, AAIM, 2006, pp. 354-366.
  [doi] [search]

• “Tight approximation algorithms for maximum general assignment problems”, Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko, SODA, 2006, pp. 611-620.
  [doi.acm.org] [search]

• “Coordination Mechanisms for Selfish Scheduling”, Nicole Immorlica, Li Li, Vahab S. Mirrokni, Andreas Schulz, WINE, 2005, pp. 55-69.
  [doi] [search]

• “Cycle Cover with Short Cycles”, Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni, STACS, 2005, pp. 641-653.
  [search]

• “Limitations of cross-monotonic cost sharing schemes”, Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni, SODA, 2005, pp. 602-611.
  [doi.acm.org] [search]

• “Power Optimization for Connectivity Problems”, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, IPCO, 2005, pp. 349-361.
  [doi] [search]

• “Sink Equilibria and Convergence”, Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta, FOCS, 2005, pp. 142-154.
  [doi.ieeecomputersociety.org] [search]

• “Subjective-Cost Policy Routing”, Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, Rahul Sami, WINE, 2005, pp. 174-183.
  [doi] [search]

• “Traffic engineering of management flows by link augmentations on confluent trees”, Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Seffi Naor, Baruch Schieber, SPAA, 2005, pp. 289-298.
  [doi.acm.org] [search]

• “A Simple Polynomial Time Framework For Reduced Path Decomposition in Multi-Path Routing”, Marina Thottan, Vahab S. Mirrokni, H\, Sanjoy Paul, INFOCOM, 2004.
  [ieee-infocom.org] [search]

• “Convergence Issues in Competitive Games”, Vahab S. Mirrokni, Adrian Vetta, APPROX-RANDOM, 2004, pp. 183-194.
  [search]

• “Distributed Network Monitoring for Evolving IP Networks”, Marina Thottan, Erran L. Li, Bin Yao, Vahab S. Mirrokni, Sanjoy Paul, ICDCS, 2004, pp. 712-719.
  [csdl.computer.org] [search]

• “Locality-sensitive hashing scheme based on p-stable distributions”, Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni, Symposium on Computational Geometry, 2004, pp. 253-262.
  [doi.acm.org] [search]

• “Market sharing games applied to content distribution in ad-hoc networks”, Michel X. Goemans, Erran L. Li, Vahab S. Mirrokni, Marina Thottan, MobiHoc, 2004, pp. 55-66.
  [doi.acm.org] [search]

• “On spectrum sharing games”, Magn\'us M. Halldórsson, Joseph Y. Halpern, Erran L. Li, Vahab S. Mirrokni, PODC, 2004, pp. 107-114.
  [doi.acm.org] [search]

• “On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems”, Nicole Immorlica, David R. Karger, Maria Minkoff, Vahab S. Mirrokni, SODA, 2004, pp. 691-700.
  [doi.acm.org] [search]

• “Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks”, Mohammad Taghi Hajiaghayi, Nicole Immorlica, Vahab S. Mirrokni, MOBICOM, 2003, pp. 300-312.
  [doi.acm.org] [search]

• “The facility location problem with general cost functions”, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Vahab S. Mirrokni, Networks, vol. 42 (2003), pp. 42-47.
  [doi] [search]

• “Length-constrained path-matchings in graphs”, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Vahab S. Mirrokni, Networks, vol. 39 (2002), pp. 210-215.
  [doi] [search]

• “RoboCup-2001: The Fifth Robotic Soccer World Championships”, Manuela M. Veloso, Tucker R. Balch, Peter Stone, Hiroaki Kitano, Fuminori Yamasaki, Ken Endo, Minoru Asada, Mansour Jamzad, Sayyed Bashir Sadjad, Vahab S. Mirrokni, Moslem Kazemi, Hamid Reza Chitsaz, Abbas Heydarnoori, Mohammad Taghi Hajiaghayi, Ehsan Chiniforooshan, AI Magazine, vol. 23 (2002), pp. 55-68.
  [search]

• “A Fast Vision System for Middle Size Robots in RoboCup”, Mansour Jamzad, Sayyed Bashir Sadjad, Vahab S. Mirrokni, Moslem Kazemi, Hamid Reza Chitsaz, Abbas Heydarnoori, Mohammad Taghi Hajiaghayi, Ehsan Chiniforooshan, RoboCup, 2001, pp. 71-80.
  [link.springer.de] [search]

• “K_r-Free Uniquely Vertex Colorable Graphs with Minimum Possible Edges”, Saeed Akbari, Vahab S. Mirrokni, Sayyed Bashir Sadjad, J. Comb. Theory, Ser. B, vol. 82 (2001), pp. 316-318.
  [doi] [search]

• “On the simultaneous edge-coloring conjecture”, Mohammad Taghi Hajiaghayi, Ebadollah S. Mahmoodian, Vahab S. Mirrokni, Amin Saberi, Ruzbeh Tusserkani, Discrete Mathematics, vol. 216 (2000), pp. 267-272.
  [doi] [search]