Algorithms - Microsoft Research

Publication

A Sketch-Based Distance Oracle for Web-Scale Graphs

Sreenivas Gollapudi, Marc Najork, Rina Panigrahy, Atish Das Sarma

3rd ACM International Conference on Web Search and Data Mining (WSDM) | February 2010

3rd ACM International Conference on Web Search and Data Mining (WSDM)

Publication

Design is as Easy as Optimization

Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani

SIAM Journal on Discrete Mathematics | February 2010, Vol 24(1): pp. 270-286

Publication

On Symmetric Encryption and Point Obfuscation

Ran Canetti, Yael Tauman Kalai, Mayank Varia, Daniel Wichs

Theory of Cryptography Conference: Lecture Notes in Computer Science, 2010 | January 2010

Publication

People, Quakes, and Communications: Inferences from Call Dynamics about a Seismic Event and its Influences on a Population

Ashish Kapoor, Nathan Eagle, Eric Horvitz

Workshop on Artificial Intelligence for Development (AI-D), AAAI Spring Symposiumg 2010 | January 2010

Publication

On the Verification Problem for Weak Memory Models

Mohamed Faouzi Atig, Ahmed Bouajjani, Sebastian Burckhardt, Madanlal Musuvathi, Madan Musuvathi

Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages | January 2010

Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

Publication

From Program Verification to Program Synthesis

Saurabh Srivastava, Sumit Gulwani, Jeffrey S. Foster

POPL’10, January 17-23, 2010, Madrid, Spain | January 2010

Video Project Project

Publication

Continuity Analysis of Programs

Swarat Chaudhuri, Sumit Gulwani, Roberto Lublinerman

POPL’10, January 17-23, 2010, Madrid, Spain | January 2010

Publication

On the Equilibria of Alternating Move Games

Aaron Roth, Nina Balcan, Adam Tauman Kalai, Yishay Mansour

SODA ’10 Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms | January 2010

ISBN: 978-0-898716-98-6

Video

Twice-Ramanujan Sparsifiers

January 15, 2010 | Nikhil Srivastava

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can…

01:09:55

Publication

Price of Anarchy for Greedy Auctions

Brendan Lucier, Allan Borodin

Symposium on Discrete Algorithms (SODA) 2010 | January 2010