*
Quick Links|Home|Worldwide
Microsoft*
Search for
Algorithms and Theory - Silicon Valley

Overview
Contributors
Projects
Publications
Overview

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 database privacy, approximation algorithms, algorithmic mechanism design, cryptography, algorithms for large data sets and the theory of distributed computing, among others.

Contributors

Moshe Babaioff, Liad Blumrosen, Steve Chien, Cynthia Dwork, Andrew Goldberg, Dahlia Malkhi, Frank McSherry, Ilya Mironov, Aleksandrs Slivkins, Kunal Talwar, Renato Werneck.

Current Projects

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.

Algebraic Computation

We also conduct research in some aspects of pure theory; one area of recent interest involves algebraic computation and the hardness of computing the determinant of a matrix in various restricted settings. It is well-known that determinant is efficiently computable over any commutative ring, but the question of whether this remains true in a non-commutative setting is generally open. Aside from the philosophical interest in the computational power of commutativity, an answer to this question would have direct bearing on applications in approximate counting.

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.

Algorithmic Game Theory

We study several problems related to game theory. These problems are motivated by e-commerce applications and applications of game theory to computer system and network design. In mechanism design, we aim to develop mechanisms with useful properties which optimize an objective function, such as seller's revenue or global welfare of the system, in the worst- or average-case. Our work shows that techniques from learning, on-line algorithms, and coding theory can be applied to mechanism design. We also study complexity of computational problems that come up in implementations of game-theoretic mechanisms. Finally, we are interested in research problems on the borderline of Economics and Computer Science, including Game Theory, Social Networks, and Electronic Markets.

Database Privacy

Statistical databases such as are produced by the US Census contain a large volume of illuminating and potentially useful data. They also run the risk of revealing a great deal of specific information about the participants, which participants generally dislike. There is an inherent tradeoff between the utility that databases can offer and the privacy they afford their constituents. We are studying this tradeoff formally, attempting to understand the relationship between privacy and utilily, and thereby find a comfortable position between the extremes of fully disclosed and completely withheld data.

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.

Nocturnal

Nocturnal is an automated Messenger-based information sharing and collaboration web-search system. The vision behind the Nocturnal project is to harness the power of social links for sharing information such as recommendations and reviews. The key idea is to leverage the existing messaging network in order to bootstrap the system with natural, automatic social communities. The communities are formed by a user's buddies list, his buddies' buddies and their buddies, and so on. Each social circle shares much in common, without requiring users to subscribe to any new service, eliciting information about users' hobbies and social behavior, etc.

SPA

The problem of finding shortest paths in graphs is a fundamental optimization problem with many applications. Currently the SPA project focuses on the following variant of the shortest path problem. Given a graph, we prepossess it subject to the restriction that the space for the preprocessing results is limited (e.g., a small constant times the space used to store the graph). Then we would like to quickly answer queries on single-pair shortest paths. This is a natural variant of the problem as in many applications, such as that of computing driving directions (e.g., Mapquest, Microsoft Mappoint.net, Yahoo! Maps). We develop two approaches, the combination of which leads to the state of the art algorithm for the problem, both for desktops and small devises (e.g., hand-held GPS). The first approach uses heuristic search in combination with new landmark-based lower-bounding techniques. The second approach uses the concept of reach that allows the shortest path search to prune "local" vertices and concentrate on "highway" vertices. We introduce a small number of additional "express highway" arcs that do not change graph distances but reduce vertex reach and algorithm performance.

We are also involved in the 9th DIMACS Implementation Challenge: Shortest Paths .

Selected Publications

©2008 Microsoft Corporation. All rights reserved. Terms of Use |Trademarks |Privacy Statement