Vahab Mirrokni

Vahab Mirrokni is a Senior Staff Research Scientist, heading the algorithms research group 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 New York in 2008, after spending a couple of years at Microsoft Research, MIT and Amazon.com. 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. 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

  •  

    Concise Bid Optimization Strategies with Multiple Budget Constraints

    Arash Asadpour, Mohammadhossein Bateni, Kshipra Bhawalkar, Vahab Mirrokni

    WINE, The 10th Conference on Web and Internet Economics (2014) (to appear)

  •  

    Distributed Balanced Clustering via Mapping Coresets

    Mohammadhossein Bateni, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni

    NIPS, Neural Information Processing Systems Foundation (2014) (to appear)

  •  

    Multiplicative Bidding in Online Advertising

    Mohammadhossein Bateni, Jon Feldman, Vahab Mirrokni, Sam Chiu-wai Wong

    ACM Conference on Economics and Computation (EC) (2014)

  •  

    Reduce and aggregate: similarity ranking in multi-categorical bipartite graphs

    Alessandro Epasto, Jon Feldman, Silvio Lattanzi, Stefano Leonardi, Vahab Mirrokni

    WWW (2014), pp. 349-360

  •  

    A Local Algorithm for Finding Well-Connected Clusters

    Zeyuan Allen Zhu, Silvio Lattanzi, Vahab Mirrokni

    The 30th International Conference on Machine Learning, ICML 2013

  •    

    Clinching Auctions with Online Supply

    Gagan Goel, Vahab Mirrokni, Renato Paes Leme

    SODA (2013), pp. 605-619

  •    

    Diversity maximization under matroid constraints

    Zeinab Abbassi, Vahab Mirrokni, Mayur Thakur

    KDD, ACM SIGKDD (2013), pp. 32-40

  •  

    PASS Approximation: A Framework for Analyzing and Designing Heuristics.

    Uri Feige, Nicole Immorlica, Vahab Mirrokni, Hamid Nazerzadeh

    Algorithmica, vol. 450-478 (2013)

  •   

    Two-stage Robust Network Design with Exponential Scenarios

    Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour

    Algorithmica, vol. 65 (2013), pp. 391-408

  •  

    Whole-page optimization and submodular welfare maximization with online bidders

    Nikhil Devanur, Zhiyi Huang, Nitish Korula, Vahab Mirrokni, Qiqi Yan

    ACM Conference on Electronic Commerce (EC) 2013, pp. 305-322

  •   

    A Theoretical Examination of Practical Game Playing: Lookahead Search

    Vahab S. Mirrokni, Nithum Thain, Adrian Vetta

    SAGT (2012), pp. 251-262

  •   

    Budget Optimization for Online Campaigns with Positive Carryover Effects

    Nikolay Archak, Vahab S. Mirrokni, S. Muthukrishnan

    WINE (2012), pp. 86-99

  •   

    Convergence and approximation in potential games

    George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos

    Theor. Comput. Sci., vol. 438 (2012), pp. 13-27

  •   

    How to approximate optimal auctions

    Nima Haghpanah, Nicole Immorlica, Vahab S. Mirrokni, Kamesh Munagala

    SIGecom Exchanges, vol. 11 (2012), pp. 30-33

  •   

    On Fixed-Price Marketing for Goods with Positive Network Externalities

    Vahab S. Mirrokni, Sebastien Roch, Mukund Sundararajan

    WINE (2012), pp. 532-538

  •   

    On the advantage of overlapping clusters for minimizing conductance

    Rohit Khandekar, Guy Kortsarz, Vahab Mirrokni

    Proceedings of the 10th Latin American international conference on Theoretical Informatics, Springer-Verlag, Berlin, Heidelberg (2012), pp. 494-505

  •  

    On the Non-progressive Spread of Influence through Social Networks

    MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabad, Vahab Mirrokni, Sina Sadeghian

    LATIN (2012)

  •   

    Online allocation of display ads with smooth delivery

    Anand Bhalgat, Jon Feldman, Vahab S. Mirrokni

    KDD (2012), pp. 1213-1221

  •  

    Overlapping clusters for distributed computation

    Reid Andersen, David Gleich, Vahab Mirrokni

    ACM Conference on Web Search and Data Mining (WSDM) (2012)

  •   

    Polyhedral clinching auctions and the adwords polytope

    Gagan Goel, Vahab Mirrokni, Renato Paes Leme

    STOC, ACM (2012), pp. 107-122

  •  

    Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation

    Vahab Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam

    Symposium on Discrete Algorithms (SODA), ACM/SIAM (2012)

  •   

    Inner Product Spaces for MinSum Coordination Mechanisms

    Richard Cole, Jose R. Correa, Vasilis Gkatzelis, Vahab Mirrokni, Neil Olver

    STOC (2011)

  •   

    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

  •  

    Online Stochastic Weighted Matching: Improved Approximation Algorithms

    Bernard Haeupler, Vahab Mirrokni, Morteza Zadimoghaddam

    Workshop of Network and Internet Economics (WINE) 2011

  •  

    Optimal Auctions with Positive Network Externalities

    Nima Haghpanah, Nicole Immorlica, Vahab Mirrokni, K. Munagala

    ACM Conference on Electronic Commerce (2011)

  •    

    Yield Optimization of Display Advertising with Ad Exchange

    Santiago Balseiro, Jon Feldman, Vahab Mirrokni, S. Muthukrishnan

    ACM Conference on Electronic Commerce (2011)

  •   

    Auctions with intermediaries: extended abstract

    Jon Feldman, Vahab S. Mirrokni, S. Muthukrishnan, Mallesh M. Pai

    ACM Conference on Electronic Commerce (2010), pp. 23-32

  •   

    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

  •   

    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

  •   

    Mining advertiser-specific user behavior using adfactors

    Nikolay Archak, Vahab S. Mirrokni, S. Muthukrishnan

    WWW (2010), pp. 31-40

  •   

    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

  •   

    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

  •   

    Optimal marketing and pricing over social networks

    Nicole Immorlica, Vahab S. Mirrokni

    WWW (2010), pp. 1349-1350

  •  

    Quasi-Proportional Mechanisms: Prior-free Revenue Maximization

    Vahab S. Mirrokni, S. Muthukrishnan, Uri Nadav

    Latin (2010), to appear

  •  

    Approximating Submodular Functions Everywhere

    Michel Goemans, Nick Harvey, S. Iwata, Vahab Mirrokni

    Symposium on Discrete Algorithms (SODA) (2009)

  •   

    Bid optimization for broad match ad auctions

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

    WWW (2009), pp. 231-240

  •   

    Competitive Routing over Time

    Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, Shang-Hua Teng

    Workshop of Internet Economics (WINE) (2009), pp. 18-29

  •   

    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

  •   

    Non-monotone submodular maximization under matroid and knapsack

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

    STOC (2009), pp. 323-332

  •   

    On the complexity of nash dynamics and sink equilibria

    Vahab S. Mirrokni, Alexander Skopalik

    ACM Conference on Electronic Commerce (2009), pp. 1-10

  •   

    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

  •   

    Online Stochastic Matching: Beating 1-1/e

    Jon Feldman, Aranyak Mehta, Vahab Mirrokni, S. Muthukrishnan

    Symposium on the Foundations of Computer Science (FOCS) (2009)

  •   

    PASS Approximation

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

    APPROX-RANDOM (2009), pp. 111-124

  •   

    Tutorial summary: Convergence of natural dynamics to equilibria

    Eyal Even-Dar, Vahab S. Mirrokni

    ICML (2009), pp. 173

  •   

    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

  •   

    Two-Stage Robust Network Design with Exponential Scenarios

    Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour

    ESA (2008), pp. 589-600

Previous Publications

  •   

    Secure Overlay Network Design

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

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

  •   

    (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{\'a}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 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{\'a}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{\'u}s M. Halld{\'o}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

  •   

    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

  •   

    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