Mark M. Wilde holds the Ph.D. degree in Electrical Engineering from the University of Southern California with a special focus in quantum computing and communication. He also holds the M.S. degree in Electrical Engineering from Tulane University and the B.S. degree in Computer Engineering from Texas A&M University. He has published over 20 articles on the theory of quantum computing and communication and has presented talks at several quantum information conferences including the recent Theory of Quantum Computation, Communication, and Cryptography Workshop held in May 2009 in Waterloo, Canada. He will be teaching an introductory graduate course on the theory of quantum communication (quantum Shannon theory) at George Washington University in Washington, DC in the Fall of 2009.

Mark M. Wilde holds the Ph.D. degree in Electrical Engineering from the University of Southern California with a special focus in quantum computing and communication. He also holds the M.S. degree in Electrical Engineering from Tulane University and the B.S. degree in Computer Engineering from Texas A&M University. He has published over 20 articles on the theory of quantum computing and communication and has presented talks at several quantum information conferences including the recent Theory of Quantum Computation, Communication, and Cryptography Workshop held in May 2009 in Waterloo, Canada. He will be teaching an introductory graduate course on the theory of quantum communication (quantum Shannon theory) at George Washington University in Washington, DC in the Fall of 2009.

Assistant professor in CS department at University of New Mexico starting in Fall 2008. Graduated from MONET Group directed by Professor Klara Nahrstedt at University of Illinois at Urbana-Champaign.

Submodular maximization is a central problem in optimization with several applications. Unlike minimizing submodular functions, submodular maximization is NP-hard. In this talk, we first describe recent approximation algorithms for this problem, and then discuss an application in optimal marketing over social networks. We give the first constant-factor approximation algorithms for maximizing non-negative submodular functions with multiple budget and matroid constraints. In particular, we give a randomized 2/5- approximation algorithm for maximizing non-negative submodular functions and a 1/5-approximatin for maximizingsubmodular functions with multiple budget constraints. Furthermore, we prove that achieving an approximation factor better than 1/2 requires exponential time.

In the second half of the talk, I will discuss an application in marketing digital goods over social networks, and study revenue- maximizing marketing strategies in the presence of positive network externalities of buyers. In particular, we study a set of influence- and-exploit marketing strategies and show how to use submodualr maximization to identify a set of influential buyers in a social network.

This talk is based on joint work with Feige and Vondrak (FOCS 2007), Hartline and Sundararajan (WWW 2008), and Lee, Nagarajan, Sviridenko (STOC 2009).

Vahab Mirrokni is a Senior Research Scientist at Google Research in New York. He joined Google after receiving a B.Sc. from Sharif University in 2001 and a Ph.D. from MIT in 2005, one year at MIT and Amazon.com, and two years at Microsoft Research. Vahab is co-winner of the SODA 2005 best student paper award and the ACM EC 2008 best paper award. He has published more than 55 papers in journals and conferences and has filed 12 patents in these areas. Vahab's research interests include algorithmic game theory, approximation algorithms, and the Internet Economics. At Google, he is working on various algorithmic and economic problems related to the Internet search and online advertisement.

I will talk about the problem of efficiently transmitting quantum states through a network. It has been known for some time that without additional assumptions it is impossible to achieve this task perfectly in general --- indeed, it is impossible even for the simple butterfly network. In this work, as additional resource free classical communication between any pair of network nodes is allowed. I will show that perfect quantum network coding is achievable in this model whenever classical network coding is possible over the same network when replacing all quantum capacities by classical capacities.

This is a joint work with Hirotada Kobayashi, Harumichi Nishimura and Martin Roetteler. A preliminary version of the results can be found here.