Publications

Working Papers

• Online Ad Assignment with Free Disposal Joint with J. Feldman, N. Koroula, S. Muthukrishnan and M. Pal
  
  
  
• Quasi-proportional Mechanisms: Prior-free Revenue Maximization Joint with S. Muthukrishnan and U. Nadav
  
  
  
• Overlapping vs. Non-overlapping Clustering: Conductance and Density Joint with R. Khandekar and G. Kortsarz
  
  
  
• Iterative Pricing with Positive Network Externalities Joint with H. Akhlaghpour, M. Ghodsi, N. Haghpanah, H. Mahini, A. Nikzad.
  5th Workshop on Ad Auctions, Stanford, 2009.
  
  
• Selfish Routing Over Time Joint with M. Hoefer, H. Roeglin, S. Teng
  NetEcon Workshop, Stanford, 2009.
  
  
• Overlapping Clustering for Distributed Computation, Joint with R. Andersen
  
  
  

  Journals and Refereed Conferences

  2009

• Online Stochastic Matching: Beating 1-1/e Joint with J. Feldman, A. Mehta, and S. Muthukrishnan
  IEEE Foundations of Computer Science (FOCS), 2009.
  
  
• On the Complexity of Nash Dynamics and Sink Equilibria, Joint with A. Skopalik
  ACM Conference on Electronic Commerce (EC), 2009.
  
  
• PASS Approximations: A New Framework for Analyzing Heuristics, Joint with U. Feige, N. Immorlica, and H. Nazerzadeh
  Approximation Algorithms and Combinatorial Optimization (APPROX), 2009.
  
  
• Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints, Joint with J. Lee, V. Nagarajan, M. Sviridenko
  Symposium of Theory of Computing (STOC), 2009.
  
  
• Bid Optimization for Broad-Match Ad Auctions, Joint with E. Even-dar, Y. Mansour, M. Muthukrishnan, U. Nadav
  18th Int. World Wide Web Conference (WWW), 2009.
  
  
• Approximating Submodular Functions Everywhere, Joint with M. Goemans, N. Harvey, and S. Iwata
  Symposium of Discrete Algorithms (SODA), 2009. [ PDF File ]
  
  

  2008

• Robust Network Design with Exponential Scenarios, joint with R. Khandekar, G. Kortsarz, M. Salavatipour
  Eureapean Symposium of Algorithms (ESA) 2008. [ PDF File ]
  
  
• Uncoordinated Two-sided Markets 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.
  
  
• Fast Convergence to Nearly Optimal Solutions in Potential Games, Joint with B. Awerbuch, Y. Azar, and A. Epstein, A. Skopalik
  ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]
  
  
• Tight Information-Theoretic Lower Bounds for Combinatorial Auctions, Joint with M. Schapira and J. Vondrak
  ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]
  
  
• Singleton Betting for Permutation Betting Markets, Joint with M. Ghodsi, H. Mahini, M. Zadi-moghaddam
  ACM Conference on Electronic Commerce (EC), 2008. [ PDF File ]
  
  
• The Myth of the Folk Theorem , Joint with C. Borgs, J. Chayes, N. Immorlica, A. Kalai, and C. Papadimitriou
  ACM Symposium of Theory of Computing (STOC) 2008 [ PDF File ]
  
  
• On the Stability of Web Crawling and Web Search, Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, and S. Teng
  19th International Symposium on Algorithms and Computation (ISAAC), 2008. [ PDF File ]
  
  
• Optimal Marketing Strategies over Social Networks, Joint with J. Hartline and M. Sundararajan
  17th International World Wide Web Conference (WWW), 2008 [ PDF File ]
  
  
• A Combinatorial Allocation Mechanism for Banner Advertisment with Penalties, Joint with U. Feige, N. Immorlica, and H. Nazerzadeh
  17th International World Wide Web Conference (WWW), 2008 [ PDF File ]
  
  
• Trust-based Recommendation Systems: an Axiomatic Approach, Joint with R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, A. Kalai, and M. Tennenholtz
  17th International World Wide Web Conference (WWW), 2008. [ PDF File ]
  
  
• Robust PageRank and Locally Computable Link Spam Fea\ tures, Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, K. Jain and\ S. Teng
  International Workshop on Adverserial Information Retreival on the Web (AirWeb) , 2008. [ PDF File ]
  
  
• Improved Approximation Algorithms for Minimum Power Connectivity Problems, Joint with G. Kortsarz, Z. Nutov, and E. Tsanko
  8th Latin American Theoretical Informatics (LATIN), 2008 [ PDF File ]
  
  
• Optimal Coordination Mechanisms for Unrelated Machine Scheduling Joint with Y. Azar and K. Jain
  Symposium on Discrete Algorithms (SODA), 2008 [ PDF File ]
  
  

  2007

• Maximizing Non-monotone Submodular Functions , Joint with U. Feige and J. Vondrak
  Foundations of Computer Science (FOCS), 2007 [ PDF File ]
  
  
• A Unified Approach to Congestion Games and Two-sided Markets Joint with H. Ackermann, P. Goldberg, H. Roeglin, and B. Voecking
  Workshop of Internet Economics (WINE), 2007 [ PDF File ]
  
  
• Local Computation of PageRank Contributions Joint with R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, and\ S. Teng
  Workshop of Graph Models of the Web (WAW), 2008. [ PDF File ] Journal version, to appear Internet Mathematics Journal.
  
  
• Robust Combinatorial Optimization with Exponential Scenarios, Joint with U. Feige, K. Jain and M. Mahdian,
  Integer Programming and Combinatorial Optimization (IPCO), 2007 [ PDF File ]
  
  
• A Recommendation System Based on Random Walks and Spectral Methods, Joint with Z. Abbassi
  Workshop of Web Mining and Social Network Analysis(WebKDD), 2007
  
  

  2006

• Assignment Problems in Rental Markets, Joint with D. Abraham, N. Chen and V. Kumar,
  2nd Workshop of Internet Economics, WINE, 2006 [ PDF File ]
  
  
• Cell Breathing in Wireless LANs: Algorithms and Evaluation Joint with V. Bahl, M. Hajiaghayi, K. Jain, L. Qiu, A. Saberi
  IEEE Transaction on Mobile Computing, 2008. [ PDF File ]
  
  
• Convergence and Approximation in Potential Games , Joint with G. Christodolou and A. Sidiropolous
  Symposium on Theoretical Aspects of Computer Science (STACS), 2006 [ PS File ]
  
  
• Overlay Secure Network Design , Joint with L. Li and M. Mahdian
  Journal Version to appear Algorithmica 2008. Algorithmic Aspects in Information and Management (AAIM) 2006. [ PS File ]
  
  
• (Almost) Tight Approximation Algorithms for Maximizing General Assignment Problems. Joint with L. Fleischer, M. Goemans, and M. Sviridenko
  Symposium on Discrete Algorithms (SODA), 2006 [ PS File ]
  
  

  2005

• Sink Equilibria and Convergence, Joint with M. Goemans and A. Vetta,
  Foundations of Computer Science(FOCS), 2005. [ PS File ]
  
  
• A Relation between Choosability and Uniquely List Colorability, Joint with S. Akbari, B.S. Sadjad.
  Journal of Combinatorial Theory, Ser. B . [ PS File ]
  
  
• Bandwidth Sharing VPN Network Design for Multi-class Traffic with Application to VoIP, Joint with M. Hajiaghayi, L. Li, and M. Thottan
  INFOCOM, 2006.
  
  
• Power Optimization for Connectivity Problems, , Joint with M. Hajiaghayi, G. Kortsarz and Z. Nutov,
  Integer Programming and Combinatorial Optimization(IPCO), 2005. [ PS File ]
  
  
• Coordination Mechanisms for Selfish Scheduling , Joint with N. Immorlica, L. Li, and A. Schulz
  Workshop of Internet Economics(WINE), 2005. [ PDF File ]
  
  
• Subjective Cost Policy Routing , Joint with J. Feigenbaum, D. Karger, and R. Sami
  Workshop of Internet Economics(WINE), 2005. Journal Version Theoretical Computer Science 2007. [ PS File ]
  
  
• Confluent Flow Augmentaion for Data Traffic Engineering, Joint with R. Bahtia, N. Immorlica, T. Krimbel, S. Naor, and B. Scheiber,
  SPAA, 2005. [ PS File ]
  
  
• Cycle Cover with short cycles , Joint with N. Immorlica and M. Mahdian
  Symposium on Theoretical Aspects of Computer Science (STACS), 2005. [ PDF File ]
  
  
• On the limitations of the Cross-monotone Cost Sharings. , Joint with N. Immorlica and M. Mahdian
  Symposium on Discrete Algorithms (SODA), 2005. [ PS File ]
  Winner of the Best Student Paper Award.
  
  

  2004

• Convergence Issues in Competitive Games , Joint with A. Vetta
  APPROX 2004.[ PS File ]
  
  
• On Spectrum Sharing Games , Joint with J. Halpern, M. Halldorson, L. Li.
  PODC 2004. [ PS File ]
  
  
• On the Costs and Benefits of Procrastination: Approximation Algorithms for Stochastic Combinatorial Optimization Problems , joint with N. Immorlica, D. Karger and M. Minkoff.
  Symposium on Discrete Algorithms (SODA), 2004.[ PS File ]
  
  
• Locality-Sensitive Hashing Scheme Based on $p$-Stable Distributions , Joint with M. Datar, N. Immorlica and P. Indyk
  SoCG 2004.
  Abstract appeared in Dimacs workshop on Streaming Data Analysis, March 2003, Rutgers University [ PS File ]
  
  
• Fault-tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks , Joint with M. Bahramgiri; M. Hajiaghayi
  ACM/Kluwer Wireless Networks, to appear.
  A preliminary version of this paper has appeared in the Proc. the 11th IEEE International Conference on Computer Communications and Networks (IC3N), October 14-16, 2002, Miami, Florida, pp. 392-398. [ PS File ]
  
  
• Market Sharing games applied to Content Distribution in Ad-Hoc Networks , Joint with M. Goemans, L. Li, M. Thottan.
  MOBIHOC 2004. [ PS File ]
  
  
• A Simple Polynomial Time Framework To Reduced Path Decomposition in Multi-Path Routing , Joint with M. Thottan, H. Uzunalioglu and S. Paul
  INFOCOM 2004. [ PS File ]
  
  

  2003

• Power Optimization in Topology Control Algorithms for Wireless Multihop networks, joint with M. Hajiaghayi and N. Immorlica,
  MOBICOM 2003. An extended version of this paper is accepted to IEEE/ACM Transactions on Networking. [ PS File ]
  
  
• The Facility location problem with general cost functions , 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 ]
  
  

  2002

• Path Matching Problems with length constraints, Joint with M. Ghodsi, M.T.Hajiaghayi, M. Mahdian.
  Networks, Vol 39/4(2002). pp 210-215. [ PS File ]
  
  
• Scalable Network Monitoring for Evolving IP Networks , Joint with L. Li, M. Thottan, B. Yao and S. Paul
  ICDCS 2004. [ PS File ]
  
  

  2001

• Uniquely Vertex Colorable Graphs with Minimum Possible Edges, Joint with S. Akbari, B.S. Sadjad.
  Journal of Combinatorial Theory Ser. B, 82 (2001) no.2, 316--318. [ PS File ]
  
  

  2000

• On Simultaneous Edge Coloring of Graphs, joint with M.T. Hajiaghaee, E.S.Mahmoodian, A. Saberi, R. Tusserkani
  Discrete Mathematics 216(2000), pp267-272.
  
  

  Book Chapters

• A book chapter on Content Distribution and Two-sided Markets, in Encyclopedia of Algorithms.
• A book chapter on Nearest Neighbor Methods in Learning and Vision Joint with A. Andoni, M. Datar, N. Immorlica, and P. Indyk.
• Iranian Informatics Olympiad , Joint with M.T. Hajiaghayi and Y. Ahmadi, Young Scholars Club Pub. Sept, 2000.

  PhD Thesis

• Approximation Algorithms for Distributed and Selfish Agents , Massachusetts Institute of Technology, June, 2005. [ PS File ]

  Robotics and Image Processing

• A Fast Vision System for Middle Size Robots in RoboCup, joint with Sharif CE RoboCup (2001) team members.
  Lecture Notes in Computer Science 2377: RoboCup2001, Robot Soccer World Cup V.. [ PS File ]
  This paper was selected as the best Engineering Challenge in RoboCup 2001.
  
  
• An omni-directional vision system for localization and object detection in middle size RoboCup, Joint with M. Jamzad and A. Hadjkhodabakhshi.
  IASTED International Conference: Modeling and Simulation, Cambridge, USA, Sept. 2001. [ PDF File ]
  
  
• Basic Requirements for a Teamwork in Middle Size RoboCup, Joint with Sharif CE RoboCup (2001) team members.
  Lecture Notes in Computer Science 2377: RoboCup2001, Robot Soccer World Cup V. [ PS File ]
  
  
• A Goal Keeper for Middle-Size Robocup, joint with Sharif CE RoboCup team members,
  Lecture Notes in Computer Science 2019: RoboCup2000, Robot Soccer World Cup IV.
  
  
• RoboCup-2001 -The Fifth Robotic Soccer World Championships. Joint with SharifCE Robocup team,
  AI magazine, Vol. 23, No. 1, pp. 55-68, 2002.