Vahab S. Mirrokni

Vahab Mirrokni is a principal scientist, heading the algorithms research groups at Google Research, New York. He received his PhD from MIT in 2005 and his B.Sc. from Sharif University of Technology in 1999. He joined Google Research in 2008, after spending a couple of years at Microsoft Research, MIT and Amazon.com. He is the co-winner of paper awards at KDD'15, ACM EC'08, and SODA'05. His research areas include algorithms, distributed and stochastic optimization, and computational economics. At Google, he is mainly working on algorithmic and economic problems related to search and online advertising. Recently he is working on online ad allocation problems, distributed algorithms for large-scale graph mining, and mechanism design for advertising exchanges. He also has a personal homepage.

Google Publications

Previous Publications

  •  

    On non-progressive spread of influence through social networks

    MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabadi, Vahab S. Mirrokni, Sina Sadeghian Sadeghabad

    Theor. Comput. Sci., vol. 550 (2014), pp. 36-50

  •  

    Tight Approximation Algorithms for Maximum Separable Assignment Problems

    Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko

    Math. Oper. Res., vol. 36 (2011), pp. 416-431

  •  

    Coordination Mechanisms for Weighted Sum of Completion Times in Machine Scheduling

    Richard Cole 0001, Vasilis Gkatzelis, Vahab S. Mirrokni

    CoRR, vol. abs/1010.1886 (2010)

  •  

    Online Stochastic Ad Allocation: Efficiency and Fairness

    Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, Clifford Stein

    CoRR, vol. abs/1001.5076 (2010)

  •   

    Secure Overlay Network Design

    Li (Erran) Li, Mohammad Mahdian, Vahab S. Mirrokni

    Algorithmica, vol. 57 (2010), pp. 82-96

  •  

    Bid Optimization in Broad-Match Ad Auctions

    Eyal Even-Dar, Yishay Mansour, Vahab S. Mirrokni, S. Muthukrishnan, Uri Nadav

    CoRR, vol. abs/0901.3754 (2009)

  •  

    Non-monotone submodular maximization under matroid and knapsack constraints

    Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko

    CoRR, vol. abs/0902.0353 (2009)

  •  

    Non-monotone submodular maximization under matroid and knapsack constraints

    Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko

    STOC (2009), pp. 323-332

  •   

    (Almost) optimal coordination mechanisms for unrelated machine scheduling

    Yossi Azar, Kamal Jain, Vahab S. Mirrokni

    SODA (2008), pp. 323-332

  •   

    A combinatorial allocation mechanism with penalties for banner advertising

    Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh

    WWW (2008), pp. 169-178

  •   

    Approximating Minimum-Power Degree and Connectivity Problems

    Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko

    LATIN (2008), pp. 423-435

  •   

    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

  •   

    Limitations of cross-monotonic cost-sharing schemes

    Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni

    ACM Transactions on Algorithms, vol. 4 (2008)

  •   

    Market Games and Content Distribution

    Vahab S. Mirrokni

    Encyclopedia of Algorithms (2008)

  •   

    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

  •   

    Optimal marketing strategies over social networks

    Jason D. Hartline, Vahab S. Mirrokni, Mukund Sundararajan

    WWW (2008), pp. 189-198

  •   

    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

  •   

    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

  •   

    Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions

    Vahab S. Mirrokni, Michael Schapira, Jan Vondrák

    ACM Conference on Electronic Commerce (2008), pp. 70-77

  •   

    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

  •   

    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

  •  

    A Recommender System Based on Local Random Walks and Spectral Methods

    Zeinab Abbassi, Vahab S. Mirrokni

    WebKDD/SNA-KDD (2007), pp. 139-153

  •   

    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

  •   

    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

  •   

    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

  •   

    Maximizing Non-Monotone Submodular Functions

    Uriel Feige, Vahab S. Mirrokni, Jan Vondrák

    FOCS (2007), pp. 461-471

  •   

    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

  •   

    Robust Combinatorial Optimization with Exponential Scenarios

    Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab S. Mirrokni

    IPCO (2007), pp. 439-453

  •   

    Subjective-cost policy routing

    Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, Rahul Sami

    Theor. Comput. Sci., vol. 378 (2007), pp. 175-189

  •   

    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

  •   

    Assignment Problems in Rental Markets

    David Abraham, Ning Chen, Vijay Kumar, Vahab S. Mirrokni

    WINE (2006), pp. 198-213

  •   

    Bandwidth Sharing Network Design for Multi-Class Traffic

    Mohammad Taghi Hajiaghayi, Li Li, Vahab S. Mirrokni, Marina Thottan

    INFOCOM (2006)

  •   

    Convergence and Approximation in Potential Games

    George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos

    STACS (2006), pp. 349-360

  •   

    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

  •   

    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

  •   

    Secure Overlay Network Design

    Erran L. Li, Mohammad Mahdian, Vahab S. Mirrokni

    AAIM (2006), pp. 354-366

  •   

    Tight approximation algorithms for maximum general assignment problems

    Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko

    SODA (2006), pp. 611-620

  •   

    Coordination Mechanisms for Selfish Scheduling

    Nicole Immorlica, Li Li, Vahab S. Mirrokni, Andreas Schulz

    WINE (2005), pp. 55-69

  •  

    Cycle Cover with Short Cycles

    Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni

    STACS (2005), pp. 641-653

  •   

    Limitations of cross-monotonic cost sharing schemes

    Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni

    SODA (2005), pp. 602-611

  •   

    Power Optimization for Connectivity Problems

    Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov

    IPCO (2005), pp. 349-361

  •   

    Sink Equilibria and Convergence

    Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta

    FOCS (2005), pp. 142-154

  •   

    Subjective-Cost Policy Routing

    Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, Rahul Sami

    WINE (2005), pp. 174-183

  •   

    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

  •   

    A Simple Polynomial Time Framework For Reduced Path Decomposition in Multi-Path Routing

    Marina Thottan, Vahab S. Mirrokni, H{\, Sanjoy Paul

    INFOCOM (2004)

  •  

    Convergence Issues in Competitive Games

    Vahab S. Mirrokni, Adrian Vetta

    APPROX-RANDOM (2004), pp. 183-194

  •   

    Distributed Network Monitoring for Evolving IP Networks

    Marina Thottan, Erran L. Li, Bin Yao, Vahab S. Mirrokni, Sanjoy Paul

    ICDCS (2004), pp. 712-719

  •   

    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

  •   

    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

  •   

    On spectrum sharing games

    Magnús M. Halldórsson, Joseph Y. Halpern, Erran L. Li, Vahab S. Mirrokni

    PODC (2004), pp. 107-114

  •   

    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

  •   

    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

  •   

    The facility location problem with general cost functions

    Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Vahab S. Mirrokni

    Networks, vol. 42 (2003), pp. 42-47

  •   

    Length-constrained path-matchings in graphs

    Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Vahab S. Mirrokni

    Networks, vol. 39 (2002), pp. 210-215

  •  

    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

  •   

    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

  •  

    Basic Requirements for a Teamwork in Middle Size RoboCup

    Mansour Jamzad, Hamid Reza Chitsaz, Amirali Foroughnassiraei, Reza Ghorbani, Moslem Kazemi, Vahab S. Mirrokni, Sayyed Bashir Sadjad

    RoboCup (2001), pp. 621-626

  •   

    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

  •  

    A Goal Keeper for Middle Size RoboCup

    Mansour Jamzad, Amirali Foroughnassiraei, Mohammad Taghi Hajiaghayi, Vahab S. Mirrokni, Reza Ghorbani, Abbas Heydarnoori, Moslem Kazemi, Hamid Reza Chitsaz, Farid Mobasser, Mohsen Ebrahimi Moghaddam, M. Gudarzi, N. Ghaffarzadegan

    RoboCup (2000), pp. 583-586

  •   

    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