Publications

 

   Some Working Papers


  1. Online Submodular Welfare Maximization on a Random Order, Joint with N. Korula, and M. ZadiMoghaddam.


  1. ASYMP: A Fault-tolerant ASYnchronous Message-Passing Framework for Graph Algorithms Joint with E. Fleury and S. Lattanzi

  2. PASS Approximations: A New Framework for Analyzing Heuristics, Joint with U. Feige, N. Immorlica, and H. Nazerzadeh, Extended Abstract appeared in Approximation Algorithms and Combinatorial Optimization (APPROX), 2009. Journal Version Accepted to Algorithmica [ PDF File ]


    1. Connected Components in MapReduce and Beyond Joint with R. Kiveris, S. Lattanzi, V. Rastogi, and S. Vassilviski

       Refereed Conferences and Journals


    1. Balanced Partitioning via Linear Embedding

    1. Joint with K. Aydin and H. Bateni
      WSDM 2016.

    2. Online Submodular Welfare Maximization on a Random Order: Greedy beats 1/2

    1. Joint with N. Korula and M. ZadiMohaddam
      STOC 2015.

    2. Randomized Compsosable Core-sets for Distributed Submodular Maximization

    1. Joint with M.ZadiMoghaddam
      STOC 2015.

    2. Robust Price of Anarchy Bounds via LP and Fenchel Duality

    1. Joint with J. Kulkarni
      SODA 2015.

    2. Mapping Core-sets for Distributed Balanced Clustering,

    1. Joint with H. Bateni, A. Bhaskara, S. Lattanzi
      NIPS 2014.

    2. Coordination Mechanisms for (Selfish) Routing over Time on a Tree

    1. Joint with S. Bhattacharya, and J. Kulkarni
      ICALP 2014.

    2. Multiplicative bidding in online advertising

    1. Joint with H. Bateni, J. Feldman, and S. Wong
      ACM Conference on Economics and Computation (EC) 2014.

    2. Clinching Auctions beyond Hard Budget Constraints

    1. Joint with G. Goel and R. Paes Leme
      ACM Conference on Economics and Computation (EC) 2014.

    2. Consice Bidding Strategies with Mutiple Budget Constraints

    1. Joint with A. Asadpour, H. Bateni, K. Bhalwakar
      Conference on Web and Internet Economics (WINE) 2014.

    2. Optimal Revenue-sharing Double Auctions with applications to Ad Exchnages

    1. Joint with R. Gomes
      World Wide Web Conference (WWW) 2014.

    2. Reduce and Aggregate: Multi-categorical similarity ranking in bipartite graphs

    1. Joint with A. Epasto, J. Feldman, S. Lattanzi, S. Leonardi
      World Wide Web Conference (WWW) 2014.

    2. Composable Core-sets for Diversity and Coverage Maximization

    1. Joint with P. Indyk, S. Mahabadi, M. Mahdian
      ACM Conference on Principles of Database Systems (PODS) 2014.

    2. Partner Tiering in Display Advertising

    1. Joint with A. Balghat, N. Korula, H. Leontyef, M. Lin
      ACM Conference on Web Search and Data Mining (WSDM) 2014.

    2. Clinching Auctions with Online Supply

    1. Joint with G. Goel and R. Paes Leme
      Symposium on Discrete Algorithms (SODA), 2013.

    2. Diversity Maximization Under Matroid Constraints

    1. Joint with Z. Abbassi and M. Thakur
      ACM Conference on Knoweledge Discovery and Data Mining (KDD), 2013.

    2. Whole-Page Ad Allocation and Submodular Welfare Maximization for Online Bidders

    1. Joint with N. Devanur, Z. Huan, N. Korula, and Q. Yan
      ACM Conference on Ellectronic Commerce (EC), 2013.

    2. A Local Algorithm for Finding Well-Connected Clusters

    1. Joint with Z. Zhu, S. Lattanzi
      International Conference on Machine Learning (ICML), 2013.

    2. Polyhedral Clinching Auctions and the AdWords Polytope,

    1. Joint with G. Goel and R. Paes Leme
      Symposium on Theory of Computing (STOC), 2012.

    2. Simultaneous Approximations of Adversarial and Stochastic Budgeted Allocation Problems,

    3. Joint with S. OveisGharan and M. ZadiMoghaddam
      Symposium on Discrete Algorithms (SODA), 2012.

    1. Online Ad Allocation with Smooth Delivery

    1. Joint with A. Balghat and J. Feldman
      ACM Conference on Knoweledge Discovery and Data Mining (KDD), 2012.

    2. Budget Optimization for Online Advertising Campaigns with Carryover Effects

    1. Joint with N. Archak and S. Muthukrishnan
      Workshop of Internet and Networks Economics (WINE), 2012.

    2. On the Implications of Lookahead Search in Game Playing

    1. Joint with N. Thain and A. Vetta
      Symposium of Algorithmic Game Theory (SAGT), 2012.

      Overlapping Clustering for Distributed Computation

    1. Joint with R. Andersen and D. Gleich
      ACM Conference on Web Search and Data Mining (WSDM), 2012.

    2. On the Non-Progressive Spread of Influence over Social Networks

    3. Joint with M. Fazli, M. Ghodsi, J. Habib, P. Jalaly, S. Sadeghian.
      8th Latin American Theoretical Informatics (LATIN), 2012. .

    4. On Fixed-Priced Marketing with Positive Network Externalities

    1. Joint with S. Roch, and M. Sundurarajan
      Workshop of the Internet and Network Economics (WINE), 2012.

    2. On the advantages of overlapping vs. non-overlapping clustering for minimizing conductance,

    3. Joint with R. Khandekar, G. Kortsarz,
      8th Latin American Theoretical Informatics (LATIN), 2012. .

    4. Online Stochastic (Weighted) Matching: Improved Approximation Algorithms,

    5. Joint with B. Haeupler, M. ZadiMoghaddam
      Workshop of Networks and Internet Economics (WINE), 2011. .

    6. Inner Products for MinSum Coordination Mechanisms,

    7.    Joint with R. Cole, J. Correa, V. Gkatzelis, N. Olver
        
      Symposium on Theory of Computing (STOC), 2011.

    8. Yield Optimization of Display Advertising with Ad Exchange

    9.     Joint with S. Belsairo, J. Feldman, S. Muthukrishnan, 

    10.     ACM Conference on Electronic Commerce (EC), 2011.

    11. Optimal Auctions with Positive Network Externalities

    12.     Joint with N. Haghpanah, N. Immorlica, and K. Munagala,

    13.     ACM Conference on Electronic Commerce (EC), 2011.

    14. Auctions with Intermediaries,

    15.    Joint with J. Feldman, S. Muthukrishnan, M. Pai
         ACM Conference on Electronic Commerce (EC), 2010.

    16. Online Stochastic Packing applied to Display Ad Allocation,

    17.    Joint with J. Feldman, M. Henzinger, N. Korula, and C. Stein,

    18.    European Symposium on Algorithms (ESA), 2010.

    19. Mining Advertiser-Specific User Behaviour Using AdFactors,

    20.    Joint with N. Archak and S. Muthukrishnan
        World Wide Web Conference (WWW), 2010.

    21. Quasi-proportional Mechanisms: Prior-free Revenue Maximization,

    22.     Joint with S. Muthukrishnan and U. Nadav
          (LATIN), 2010.

    23. Iterative Pricing Over Social Networks,

    24.    Joint with H. Akhlaghpour, M. Ghodsi, N. Haghpanah, H. Mahini, A. Nikzad.

    25.    Workshop of Internet Economics (WINE) 2010. 5th Workshop on Ad Auctions, Stanford, 2009.

    26. Equilirbium Pricing with Positive Network Externalities,

    27.    Joint with H. Anari, A. Ehsani, M. Ghodsi, N. Haghpanah, N. Immorlica, H. Mahini.

    28.    Workshop of Internet Economics (WINE) 2010.

    29. Online Stochastic Matching: Beating 1-1/e,

    30.    Joint with J. Feldman, A. Mehta, and S. Muthukrishnan
         IEEE Foundations of Computer Science (FOCS), 2009.

    31. Online Ad Assignment with Free Disposal

    32.    Joint with J. Feldman, N. Koroula, S. Muthukrishnan and M. Pal
         Workshop of Internet Economics(WINE) 2009.

    33. On the Complexity of Nash Dynamics and Sink Equilibria,

    34.    Joint with A. Skopalik
         ACM Conference on Electronic Commerce (EC), 2009.

    35. Selfish Routing Over Time

    36.    Joint with M. Hoefer, H. Roeglin, S. Teng
        
      NetEcon Workshop, Stanford, 2009 and Workshop of Internet Economics (WINE) 2009.

    37. PASS Approximations: A New Framework for Analyzing Heuristics,

    38.    Joint with U. Feige, N. Immorlica, and H. Nazerzadeh.

    39.    Approximation Algorithms and Combinatorial Optimization (APPROX), 2009.

    40. Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints,

    41.    Joint with J. Lee, V. Nagarajan, M. Sviridenko,

    42.    Symposium of Theory of Computing (STOC), 2009.

    43. Bid Optimization for Broad-Match Ad Auctions,

    44.    Joint with E. Even-dar, Y. Mansour, M. Muthukrishnan, U. Nadav,

    45.    18th Int. World Wide Web Conference (WWW), 2009.

    46. Approximating Submodular Functions Everywhere,

    47.    Joint with M. Goemans, N. Harvey, and S. Iwata
         Symposium of Discrete Algorithms (SODA), 2009. [ PDF File ]

    48. Robust Network Design with Exponential Scenarios,

    49.    Joint with R. Khandekar, G. Kortsarz, M. Salavatipour
         European Symposium of Algorithms (ESA) 2008. [ PDF File ]

    50. Uncoordinated Two-sided Markets

    51.    Joint with H. Ackermann, P. Goldberg, H. Roeglin, and B. Voecking
        ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]
        Winner of the Best Paper Award.

    52. Fast Convergence to Nearly Optimal Solutions in Potential Games,

    53.    Joint with B. Awerbuch, Y. Azar, and A. Epstein, A. Skopalik
         ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]

    54. Tight Information-Theoretic Lower Bounds for Combinatorial Auctions,

    55.    Joint with M. Schapira and J. Vondrak
         ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]

    56. Singleton Betting for Permutation Betting Markets,

    57.    Joint with M. Ghodsi, H. Mahini, M. Zadi-moghaddam
         ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]

    58. The Myth of the Folk Theorem,

    59.    Joint with C. Borgs, J. Chayes, N. Immorlica, A. Kalai, and C. Papadimitriou
         ACM Symposium of Theory of Computing (STOC) 2008 [ PDF File ]

    60. On the Stability of Web Crawling and Web Search,

    61.    Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, and S. Teng,

    62.    19th International Symposium on Algorithms and Computation (ISAAC), 2008. [ PDF File ]

    63. Optimal Marketing Strategies over Social Networks,

    64.    Joint with J. Hartline and M. Sundararajan
         17th International World Wide Web Conference (WWW), 2008 [ PDF File ]

    65. A Combinatorial Allocation Mechanism for Banner Advertisment with Penalties,

    66.    Joint with U. Feige, N. Immorlica, and H. Nazerzadeh,

    67.    17th International World Wide Web Conference (WWW), 2008 [ PDF File ]

    68. Trust-based Recommendation Systems: an Axiomatic Approach,

    69.    Joint with R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, A. Kalai, and M. Tennenholtz,

    70.    17th International World Wide Web Conference (WWW), 2008. [ PDF File ]

    71. Robust PageRank and Locally Computable Link Spam Features,

    72.    Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, K. Jain and\ S. Teng,

    73.    International Workshop on Adverserial Information Retreival on the Web (AirWeb) , 2008. [ PDF File ]

    74. Improved Approximation Algorithms for Minimum Power Connectivity Problems,

    75.    Joint with G. Kortsarz, Z. Nutov, and E. Tsanko,

    76.    8th Latin American Theoretical Informatics (LATIN), 2008 [ PDF File ]

    77. Optimal Coordination Mechanisms for Unrelated Machine Scheduling

    78.    Joint with Y. Azar and K. Jain
         Symposium on Discrete Algorithms (SODA), 2008 [ PDF File ]

    79. Maximizing Non-monotone Submodular Functions ,

    80.    Joint with U. Feige and J. Vondrak
         Foundations of Computer Science (FOCS), 2007 [ PDF File ]

    81. A Unified Approach to Congestion Games and Two-sided Markets

    82.    Joint with H. Ackermann, P. Goldberg, H. Roeglin, and B. Voecking,

    83.    Workshop of Internet Economics (WINE), 2007 [ PDF File ]

    84. Local Computation of PageRank Contributions

    85.    Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, and S. Teng
         Workshop of Graph Models of the Web (WAW), 2008. [ PDF File ]

    86.    Journal version, to appear Internet Mathematics Journal.

    87. Robust Combinatorial Optimization with Exponential Scenarios,

    88.    Joint with U. Feige, K. Jain and M. Mahdian,
         Integer Programming and Combinatorial Optimization (IPCO), 2007 [ PDF File ]

    89. A Recommendation System Based on Random Walks and Spectral Methods,

    90.    Joint with Z. Abbassi
         Workshop of Web Mining and Social Network Analysis(WebKDD), 2007

    91. Assignment Problems in Rental Markets,

    92.    Joint with D. Abraham, N. Chen and V. Kumar,
         2nd Workshop of Internet Economics, WINE, 2006 [ PDF File ]

    93. Cell Breathing in Wireless LANs: Algorithms and Evaluation

    94.     Joint with V. Bahl, M. Hajiaghayi, K. Jain, L. Qiu, A. Saberi
          IEEE Transaction on Mobile Computing, 2008. [ PDF File ]

    95. Convergence and Approximation in Potential Games ,

    96.    Joint with G. Christodolou and A. Sidiropolous
         Symposium on Theoretical Aspects of Computer Science (STACS), 2006 [ PS File ]

    97. Overlay Secure Network Design ,

    98.    Joint with L. Li and M. Mahdian
        
      Journal Version to appear Algorithmica 2008. Algorithmic Aspects in Information and Management (AAIM) 2006. [ PS File ]

    99. (Almost) Tight Approximation Algorithms for Maximizing General Assignment Problems.

    100.     Joint with L. Fleischer, M. Goemans, and M. Sviridenko
          Symposium on Discrete Algorithms (SODA), 2006 [ PS File ]

    101. Sink Equilibria and Convergence,

    102.    Joint with M. Goemans and A. Vetta,
         Foundations of Computer Science(FOCS), 2005. [ PS File ]

    103. A Relation between Choosability and Uniquely List Colorability,

    104.    Joint with S. Akbari, B.S. Sadjad.
         Journal of Combinatorial Theory, Ser. B . [ PS File ]

    105. Bandwidth Sharing VPN Network Design for Multi-class Traffic with Application to VoIP,

    106.    Joint with M. Hajiaghayi, L. Li, and M. Thottan,

    107.    INFOCOM, 2006.

    108. Power Optimization for Connectivity Problems, ,

    109.    Joint with M. Hajiaghayi, G. Kortsarz and Z. Nutov,
         Integer Programming and Combinatorial Optimization (IPCO), 2005. [ PS File ]

    110. Coordination Mechanisms for Selfish Scheduling ,

    111.    Joint with N. Immorlica, L. Li, and A. Schulz
         Workshop of Internet Economics(WINE), 2005. [ PDF File ]

    112. Subjective Cost Policy Routing ,

    113.    Joint with J. Feigenbaum, D. Karger, and R. Sami
        
      Workshop of Internet Economics(WINE), 2005. Journal Version Theoretical Computer Science 2007. [ PS File ]

    114. Confluent Flow Augmentaion for Data Traffic Engineering,

    115.    Joint with R. Bahtia, N. Immorlica, T. Krimbel, S. Naor, and B. Scheiber,

    116.    SPAA, 2005. [ PS File ]

    117. Cycle Cover with short cycles ,

    118.    Joint with N. Immorlica and M. Mahdian
        
      Symposium on Theoretical Aspects of Computer Science (STACS), 2005. [ PDF File ]

    119. On the limitations of the Cross-monotone Cost Sharings. ,

    120.    Joint with N. Immorlica and M. Mahdian
         Symposium on Discrete Algorithms (SODA), 2005. [ PS File ]
         Winner of the Best Student Paper Award.

    121. Convergence Issues in Competitive Games,

    122.    Joint with A. Vetta,

    123.    APPROX 2004. [ PS File ]

    124. On Spectrum Sharing Games ,

    125.    Joint with J. Halpern, M. Halldorson, L. Li,

    126.    PODC 2004. [ PS File ]

    127. On the Costs and Benefits of Procrastination: Approximation Algorithms for Stochastic Combinatorial Optimization Problems,

    128.    Joint with N. Immorlica, D. Karger and M. Minkoff.

    129.    Symposium on Discrete Algorithms (SODA), 2004. [ PS File ]

    130. Locality-Sensitive Hashing Scheme Based on $p$-Stable Distributions,

    131.    Joint with M. Datar, N. Immorlica and P. Indyk,

    132.    SoCG 2004. [ PS File ]

    133. Fault-tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks ,

    134.    Joint with M. Bahramgiri; M. Hajiaghayi,

    135.    ACM/Kluwer Wireless Network. [ PS File ]

    136. Market Sharing games applied to Content Distribution in Ad-Hoc Networks ,

    137.    Joint with M. Goemans, L. Li, M. Thottan.

    138.    MOBIHOC 2004. [ PS File ]

    139. A Simple Polynomial Time Framework To Reduced Path Decomposition in Multi-Path Routing ,

    140.    Joint with M. Thottan, H. Uzunalioglu and S. Paul,

    141.    INFOCOM 2004. [ PS File ]

    142. Power Optimization in Topology Control Algorithms for Wireless Multihop networks,

    143.    Joint with M. Hajiaghayi and N. Immorlica,

    144.    MOBICOM 2003. IEEE/ACM Transactions on Networking. [ PS File ]

    145. The Facility location problem with general cost functions ,

    146.    Joint with M. Hajiaghayi; M. Mahdian,
         Networks 42(1), pp. 42--47, August 2003. Technical Report MIT-LCS-TR-864, MIT, March 2002. [ PS File ]

    147. Path Matching Problems with length constraints,

    148.    Joint with M. Ghodsi, M.T.Hajiaghayi, M. Mahdian.
         Networks, Vol 39/4(2002). pp 210-215. [ PS File ]

    149. Scalable Network Monitoring for Evolving IP Networks ,

    150.    Joint with L. Li, M. Thottan, B. Yao and S. Paul
         ICDCS 2004. [ PS File ]

    151. Uniquely Vertex Colorable Graphs with Minimum Possible Edges,

    152.    Joint with S. Akbari, B.S. Sadjad.
         Journal of Combinatorial Theory Ser. B, 82 (2001) no.2, 316--318. [ PS File ]

    153. On Simultaneous Edge Coloring of Graphs,

    154.    Joint with M.T. Hajiaghaee, E.S.Mahmoodian, A. Saberi, R. Tusserkani,

    155.    Discrete Mathematics 216(2000), pp267-272.


    156. PhD Thesis


    1. Approximation Algorithms for Distributed and Selfish Agents , Massachusetts Institute of Technology, June, 2005.


        Tutorials


    1. Online Ad Serving: Theory and Practice,

    2.    Joint with A. Mehta
         ACM SIGMETRICS, 2011.


    1. Ad Serving: Algorithmic Theory and Practice,

    2.    Joint with A. Mehta
         ACM Conference on Electronic Commerce (EC), 2010.

    3. Optimal Marketing and Pricing over Social Networks,

    4.    Joint with N. Immorlica
         World Wide Web Conference (WWW), 2010.

    5. Convergence of Natural Game Dynamics,

    6.    Joint with E. Even Dar
         Inernational Conference on Machine Learning (ICML), 2009.

    7. Convergence of Nash Dynamics: Equilibria and Nearly-optimal Solutions,

    8.    Joint with H. Roeglin
        
      ACM Conference on Electronic Commerce (EC), 2009.


        Book Chapters


    1. A book chapter on Content Distribution and Two-sided Markets, in Encyclopedia of Algorithms.

    2. A book chapter on Nearest Neighbor Methods in Learning and Vision Joint with A. Andoni, M. Datar, N. Immorlica, and P. Indyk.

    3. Iranian Informatics Olympiad , Joint with M.T. Hajiaghayi and Y. Ahmadi, Young Scholars Club Pub. Sept, 2000.


        Patents


    1. Online Clustering of micro-blog posts: Coverage and Diversity with Mayur Thakur.

    2. Large-scale clustering of Youtube video graph: Connectivity and Density with U. Gargi. W. Lu, S. Yoon.

    3. Online Ad Allocation with Smooth Delivery, with S. Benson, K. Chen, J. Feldman, S. Gilpin.

    4. Yield Management of Display Ad Allocation and Ad Exchange , with S. Belsairo, J. Feldman, S. Muthukrishnan.

    5. Optimal bidding strategies in online advertising with carryover effects , with N. Archak, S. Muthukrishnan.

    6. Online Stochastic Ad Allocation and Resource Allocation, with J. Feldman, M. Henzinger, N. Korula, C. Stein.

    7. Online Ad Assignment with Replacements, with J. Feldman, S. Muthukrishnan, M. Pal, N. Koroula.

    8. Graph-based Attribution in Advertising, with N. Archak, S. Muthukrishnan.

    9. Social Ad Auctions in the presence of Ad Propagation, with C. Cortes, E. Chang.

    10. Ad Allocation with Frequency Capping, with J. Feldman, S. Muthukrishnan, A. Mehta.

    11. Bid Optimization for BroadMatch Ad Auctions, with E. Even Dar, Y. Mansour, S. Muthukrishnan, U. Nadav.

    12. Offline Optimization for Online Stochastic Ad Allocation, with J. Feldman, S. Muthukrishnan, A. Mehta.

    13. Quasi-Proportional Mechanisms, with S. Muthukrishnan and U. Nadav.

    14. Optimal Marketing Strategies over Social Networks, with J. Hartline, V. Mirrokni and M. Sundararajan.

    15. Monetizing a Social Network Platform with R. Andersen, C. Borgs, J. Chayes, K. Jain, and V. Mirrokni.

    16. Trust-based Recommendation Systems with R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, V. S. Mirrokni, A. Kalai, M. Tennenholtz.

    17. Robust PageRank and Locally computable SPAM detection features with R. Andersen, C. Borgs, J. Chayes, K. Jain, J. Hopcroft, V. S. Mirrokni, S. Teng.

    18. Local Computation of PageRank Contributions, with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, V. S. Mirrokni, S. Teng.

    19. Score Propagation and Web SPAM Detection. with C. Borgs, J. Chayes, C. Gade, J. Hopcroft, V. S. Mirrokni, A. Prakash, T. Tao.

    20. Local Partitioning and Web SPAM Detection, with C. Borgs, J. Chayes, C. Gade, J. Hopcroft, V. S. Mirrokni, A. Prakash, T. Tao.

    21. Graph Structures and Web SPAM Detection, with C. Borgs, J. Chayes, C. Gade, J. Hopcroft, V. S. Mirrokni, A. Prakash, T. Tao.

    22. Optimal policies for distributed and strategic load balancing, with Y. Azar, K. Jain, and V. S. Mirrokni.

    23.  A Unified Approach to Secure Transactions and Reputation Systems, with C. Borgs, J. Chayes, K. Jain, N. Immorlica, V. S. Mirrokni.

    24. Wireless LAN Cell-Breathing, with P. Bahl, M. Hajiaghayi, K. Jain, V. Mirrokni, L. Qiu, A. Saberi.

    25. Confluent Flow Augmentation for Data Traffic Engineering, with R. Bhatia, N.Immorlica, T.Kimbrel, V. S. Mirrokni, S.Naor, and B.Schieber.
       

DBLP         Conferences and Journals      Tutorials      Patents