Morteza Zadimoghaddam

I am a PhD student in 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 have worked on Robust Online Allocation algorithms that work well in both Stochastic and Adversarial Scenarios. Based on this work, I was awarded the 2012 Yahoo! Key Scientific Challenges Scholarship. During my PhD studies, I enjoyed working as an intern in Google Research New York (summer 2012), Microsoft Research New England (summer 2011), and Microsoft Research UK (summer 2010).  You can find my resume here.

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. 











Research Interests

* Computational Advertising and Online Allocation Problems

* Approximation Algorithms and Combinatorial Optimization

* Computational Learning Theory

* Algorithmic Game Theory

* Distributed and Parallel Algorithms


Selected Publications


Online Allocation Algorithms              

· Bicriteria Online Matching: Maximizing Weight and Cardinality (joint work with Nitish Korula and Vahab Mirrokni)

· 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

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

· Learning Disjunctions: Near–Optimal Trade-offs between Mistakes and “I don’t know”s (joint work with Erik Demaine) to appear 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

· 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

· Optimal Coalition Structures in Graph Games (joint work with Yoram Bachrach, Pushmeet Kohli, and Vladimir Kolmogorov) , 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.