Vahab Mirrokni

Vahab Mirrokni is a Staff Research Scientist at Google. 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. He also has a personal homepage.

Google Publications

Clinching Auctions with Online Supply

Gagan Goel, Vahab Mirrokni, Renato Paes Leme

SODA (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
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

Vahab Mirrokni

Co-Authors

Google Publications

Previous Publications