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, cryptology (foundations of cryptography and cryptanalysis), 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

Rakesh Agrawal, Maria Christoforaki, Sreenivas Gollapudi, Anitha Kannan, Krishnaram Kenthapadi, and Adith Swaminathan, Mining Videos from the Web for Electronic Textbooks, in 12th International Conference on Formal Concept Analysis (ICFCA), Springer, June 2014

Shipra Agrawal and Nikhil R. Devanur, Bandits with concave rewards and convex knapsacks, in To appear in EC 2014, ACM conference on Economics and Computation, June 2014

Lin Xiao and Tong Zhang, A Proximal Stochastic Gradient Method with Progressive Variance Reduction, no. MSR-TR-2014-38, 18 March 2014

Rakesh Agrawal, Behzad Golshan, and Evimaria Terzi, Forming Beneficial Teams of Students in Massive Online Classes, in ACM Conference on Learning at Scale (L@S), ACM, March 2014

Dan Alistarh, James Aspnes, Valerie King, and Jared Saia, Message-passing meets shared-memory: A new approach for communication efficient randomized consensus, no. MSR-TR-2014-15, February 2014

More publications...