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.
Wednesdays 1:30 -- 2:30 PM, SVC 6/Titan. Visitors welcome. Visit seminar web page for more information.
Visit our Windows on Theory Blog
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.
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.
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.
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.
An umbrella project for several independent projects that study various MAB formulations motivated by web search and ad placement. The (basic) MAB problem is a classical problem in Machine Learning in which an online algorithm chooses from a set of strategies in a sequence of n trials so as to maximize the total payoff of the chosen strategies.
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.
Sequoia aims to make distributed applications network-aware. That is, enable applications to take advantage of the characteristics of the underlying network such as proximity, bandwidth capacity, and topology. It intends to achieve this through the key concept of prediction trees, a virtual topology of the network, where virtual nodes representing routers connect real end hosts, and carefully computed edge weights model path properties such as latency and bandwidth.
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.
Automated Messenger-based information sharing and collaboration