Morteza Zadimoghaddam

I am a research scientist at Google Research (New York office). In January 2014, I received my PhD in computer science from MIT (CSAIL) under supervision of Professor Erik D. Demaine. I work on applying optimization techniques to various practical problems in order to find provably efficient algorithms. In particular, I am interested in Online Allocation algorithms, and Submodular Optimization. During my PhD studies, I enjoyed working as an intern in Google Research Mountain View and New York (summers 2013 and 2012), Microsoft Research New England (summer 2011), and Microsoft Research UK (summer 2010).  Prior to MIT, I spent a year in EPFL university as a research assistant, and finished my Bachelor degree in Sharif University of Technology, Computer Engineering Department, Tehran-Iran. You can contact me at zadim_at_google_dot_com.  

 

 

 

 

 

 

 

 

 

 

Research Interests

* Computational Advertising and Online Allocation Problems

* Approximation Algorithms and Combinatorial Optimization

* Algorithmic Game Theory

* Distributed and Parallel Algorithms

 

Selected Publications

 

Online Allocation Algorithms              

· Online Stochastic Matching with Unequal Probabilities (joint work with Bo Waggoner and Aranyak Mehta) appeared in SODA 2015,

· Bicriteria Online Matching: Maximizing Weight and Cardinality (joint work with Nitish Korula and Vahab Mirrokni) appeared in WINE 2013,

· Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation (joint work with Vahab Mirrokni and Shayan Oveis Gharan) Appeared in SODA 2012, preprint.

· Online Stochastic Weighted Matching: Improved Approximation Algorithms (joint work with Bernhard Haeupler and Vahab Mirrokni)  Appeared in WINE 2011, preprint.

· The submodular secretary problem and its extensions (joint work with MohammadHossein Bateni and MohammadTaghi Hajiaghayi)  appeared in APPROX 2010, preprint.

Learning Algorithms and Theory

· Sparse Solutions to Nonnegative Linear Systems and Applications (joint work with Aditya Bhaskara and Ananda Theertha Suresh) to appear in AISTATS 2015.

· Efficiently Learning from Revealed Preferences (joint work with Aaron Roth) appeared in WINE 2012.

· Learning Disjunctions: Near–Optimal Trade-offs between Mistakes and “I don’t know”s (joint work with Erik Demaine) appeared in SODA 2013.

· Trading off Mistakes and Don’t Know Predictions (joint work with Amin Sayedi and Avrim Blum) appeared in NIPS 2010, preprint.

Approximation Algorithms

· How to influence people with partial incentives (joint work with E. D. Demaine, M. Hajiaghayi, H. Mahini, D. Malec, S. Raghavan, and A. Sawant), Appeared in WWW 2014,

· O(1)-Approximations for Maximum Movement Problems (joint work with P. Berman and E. Demaine), Appeared in APPROX 2011, preprint.

· Scheduling to Minimize Power Consumption using Submodular Functions  (joint work with Erik Demaine) appeared in SPAA 2010, preprint.

· Minimizing the Diameter of a Network Using Shortcut Edges (joint work with Erik Demaine) appeared in SWAT 2010, preprint.

· Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction (joint work with Mihai Badoiu, E. Demaine, M. Hajiaghayi and Anastasios Sidiropoulos) appeared in  APPROX 2008, preprint. 

· Minimizing Movement (joint work with E. Demaine, M. Hajiaghayi, H. Mahini, S. Oveis Gharan and A. Sayedi) Appeared in SODA 2007. Journal version appeared in Transactions on Algorithms, preprint.

· Scheduling to Minimize Gaps and Power Consumption (joint work with E. Demaine, M. Ghodsi, M. Hajiaghayi and A. Sayedi) Appeared in SPAA 2007, preprint.

· Spanning Trees with Minimum Weighted Degrees (joint work with M. Ghodsi, H. Mahini, K. Mirjalali, S. Oveis Gharan and A. Sayedi) in Information Processing Letters, Vol 104, Issue 3, 2007, preprint.

Algorithmic Game Theory

· Cooperative weakest link games (joint work with Yoram Bachrach, Omer Lev, Shachar Lovett, and Jeffrey S Rosenschein) appeared in AAMAS 2014  ,

· Optimal Coalition Structure Generation in Cooperative Graph Games (joint work with Yoram Bachrach, Pushmeet Kohli, and Vladimir Kolmogorov) appeared in AAAI 2013  , preprint.

· A cooperative approach to collusion in auctions (joint work with Yoram Bachrach and Peter Key)  appeared in SIGecom Exchanges 10(1), preprint.

· Constant Price of Anarchy in Network Creation Games via Public Service Advertising (joint work with Erik Demaine) appeared in WAW 2010, invited to Internet Mathematics 8(1-2), preprint.

·  Collusion in VCG Path Procurement Auctions (joint work with Yoram Bachrach and Peter Key) appeared in WINE 2010, preprint .

· The Price of Anarchy in Cooperative Network Creation Games (joint work with E. Demaine, M. Hajiaghayi and H. Mahini) appeared in SIGecom Exchanges 8(2), preliminary version appeared in STACS 2009, preprint.

· The Price of Anarchy in Network Creation Games (joint work with E. Demaine, M. Hajiaghayi and H. Mahini) appeared in ACM Transactions on Algorithms 8(2), preliminary version appeared in PoDC 2007, preprint.

· Singleton Betting for Permutation Betting Markets, (joint work with Mohammad Ghodsi, Hamid Mahini and Vahab Mirrokni), appeared in Algorithmica 60(4), preliminary version appeared in ACM EC 2008, preprint.

Distributed Algorithms

· Optimal-time adaptive strong renaming, with applications to counting. (joint work with Dan Alistarh, James Aspens, Keren Censor-Hillel, and Seth Gilbert) appeared in PoDC 2011, preprint.

· How Efficient Can Gossip Be? (On the Message Complexity of Resilient Information Exchange)  (joint work with Dan Alistarh, Seth Gilbert and Rachid Guerraoui) appeared in ICALP 2010, preprint.

· Collaborative Scoring with Dishonest Participants (joint work with Seth Gilbert, Rachid Guerraoui and Faezeh Malakouti) appeared in SPAA 2010, preprint.

Information Theory, Network Tomography

· Sequential Group Testing with Graph Constraints. (joint work with Amin Karbasi) appeared in ITW 2012.

· Compression with Graphical Constraints: An Interactive Browser (joint work with Amin Karbasi) appeared in ISIT 2011, preprint.

· On the construction of prefix-free and fix-free codes with specified codeword compositions (joint work with Ali Kakhbod) appeared in Discrete Applied Mathematics 159(18), preprint. 

· Some notes on fix-free codes, (joint work with A. Kakhbod, A. Nazari) appeared in the Proceedings of the 42nd Conference on Information Sciences and Systems (CISS 2008), preprint.

  

Honors and Awards

· Awarded Yahoo! Key Scientific Challenges Scholarship 2012: one of the winners in computational advertising challenge among all worldwide graduate student applicants, March 2012. I won this award based on my works on addressing realistic and practical challenges in computational advertising which appeared in two conferences WINE 2011 and SODA 2012.

· Awarded Neekeyfar Graduate Scholarship one of the two winners among MIT graduate students, May 2011.

· First rank in National Graduate Entrance Exam in Computer Science among more than 10,000 applicants (all graduates in computer science related fields), Tehran, Iran, 2007.

· Awarded as Outstanding Student by Sharif university president, 2003.

· Gold Medal in Iranian National Olympiad in Informatics, 2002.

· Bronze Medal in Iranian National Olympiad in Informatics, 2001.