Algorithms and Theory (Silicon Valley)

Algorithms and theory research at the Silicon Valley Campus is motivated equally by the goals of having significant impact on the real world and by advancing the state of the art in pure research. To this end, we pursue a wide variety of projects over many diverse research areas, most recently including graph algorithms, database privacy, approximation algorithms, algorithmic mechanism design, cryptography, algorithms for large data sets and the theory of distributed computing, among others.

Current Projects
  • Computational Game Theory
    We study problems in the intersection of Computer Science, Game Theory and Microeconomics. We are particularly focused on effects of strategic behavior in electronic markets, as such behavior has significant implications on the economic performance of these markets.
  • Database Privacy
    Research related to privacy issues in data analysis.
  • Learning Theory
    We work on questions motivated by machine learning, in particular from the theoretical and computational perspectives. Our goals are to mathematically understand the effectiveness of existing learning algorithms and to design new learning algorithms. We combine expertise from diverse fields such as algorithms and complexity, statistics, and convex geometry.
  • Locally decodable codes
    Highly efficient codes for data storage and transmission.
  • Multi-Armed Bandits at MSR-SVC
    This is an umbrella project for several related efforts at Microsoft Research Silicon Valley that address various Multi-Armed Bandit (MAB) formulations motivated by web search and ad placement. The MAB problem is a classical paradigm in Machine Learning in which an online algorithm chooses from a set of strategies in a sequence of trials so as to maximize the total payoff of the chosen strategies.
  • Social Algorithms at MSR-SVC
    This is an umbrella project for several related efforts at Microsoft Research Silicon Valley in the areas of social network analysis and human computation.
  • SPA
    Shortest path problems are among the most fundamental optimization problems with many applications. The project is devoted to theoretical and experimental study of algorithms for the shortest path and related problems, including single-source, feasibility, minimum mean cycle, and point-to-point shortest paths.

Other work

Algorithms for Very Large Data Sets
Data from search engine indices, search engine query logs, and instant messaging clients can be extremely useful in improving search quality and understanding social networks, but their sheer scale makes it difficult to process them using existing algorithms . We continue to design, implement, and test new algorithms for analyzing these Internet scale data sets with a view towards making search and instant messaging more effective and efficient.

Approximation Algorithms
Many natural optimization problems, such as the traveling salesman problem, are NP-hard. The area of approximation algorithms attempts to design efficient algorithms that are guaranteed to produce solutions that have cost within a small factor of the optimal. Closely related is the area of hardness of approximation: for some problems, we can prove that even getting good approximations efficiently is as hard as solving these (NP-hard) problems exactly. We are studying the design and analysis of approximation algorithms, often using tools from and contributing to the areas of metric embeddings and combinatorial optimization.

Network and Graph Algorithms
We are exploring the structure of large and dynamic networks and devising algorithms for them. This research area includes various sub-topics, including but not limited to: routing and shortest paths; network flows; locality-sensitive methods such as caching and nearest-object location; overlay networks and peer-to-peer tools; scalable information dissemination and gossip; metric embeddings.