Algorithms and Theory

Exploring game theory, market equilibriums, efficient algorithms


We are working in emerging fields within theoretical computer science, including privacy in statistical databases, and quantum computing. We also investigate algorithms and mathematics for the Internet, including web search, social-network analysis, spam fighting, and web security.

Classical areas of interest include complexity, cryptography, algebraic computation, random structures, and spectral methods for data analysis. We strive to develop scalable algorithms for learning and data mining, cryptographic algorithms, graph algorithms, synchronization algorithms, networking algorithms, and sampling algorithms. We also look at problems at the intersection of systems, networking, and algorithms research: We study the algorithmic foundations of the systems that drive today’s computing—such as cloud computing, data centers, large-scale distributed systems, and mobile computing—and we apply our expertise in practice to advance the state of the art in applied algorithm design and to deliver highly efficient, scalable, robust solutions.

We also conduct research in several theoretical areas in mathematics and physics that are beyond the traditional scope of computer science but are closely connected. Researchers actively work on combinatorics, geometry and topology, probability theory, statistical physics, number theory, and functional analysis.

Publications

Shipra Agrawal and Nikhil R. Devanur, Fast algorithms for online stochastic convex programming, in SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms), SIAM – Society for Industrial and Applied Mathematics, January 2015

Prateek Jain, Ambuj Tewari, and Purushottam Kar, On Iterative Hard Thresholding Methods for High-dimensional M-Estimation, in Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS), Neural Information Processing Systems, December 2014

Purushottam Kar, Harikrishna Narasimhan, and Prateek Jain, Online and Stochastic Gradient Methods for Non-decomposable Loss Functions, in Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS), Neural Information Processing Systems, December 2014

Edith Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Danny Raz, and Yoav Tzur, Probe Scheduling for Efficient Detection of Silent Failures, no. MSR-TR-2014-113, October 2014

James Cook, Abhimanyu Das, Krishnaram Kenthapadi, and Nina Mishra, Ranking Twitter Discussion Groups, in ACM Conference on Online Social Networks (COSN), ACM – Association for Computing Machinery, October 2014

More publications...