Algorithms - Microsoft Research

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

Publication

Structure-driven optimizations for amorphous data-parallel programs

Mario Méndez-Lojo , Donald Nguyen , Dimitrios Prountzos, Xin Sui , M. Amber Hassaan , Milind Kulkarni , Martin Burtscher , Keshav Pingali

Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) | January 2010

Publication

Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions

Brendan Lucier

Innovations in Theoretical Computer Science (ITCS) 2010 | January 2010

Publication

Survivable Virtual Network Embedding

Muntasir Raihan Rahman, Issam Aib, Raouf Boutaba

NETWORKING 2010 | January 2010

Publication

Incentives in Online Auctions via Linear Programming

Niv Buchbinder, Kamal Jain, Mohit Singh

In Proceedings of Sixth Workshop on Internet and Network Economics (WINE) | January 2010

Publication

Dimensions in Program Synthesis

Sumit Gulwani

PPDP ’10 Hagenberg, Austria | January 2010

Project

Publication

Game-theoretic Models of Information Overload in Social Networks

Christian Borgs, Jennifer Chayes, Brian Karrer, Brendan Meeder, R. Ravi, Ray Reagans, Amin Sayedi

Proceedings of the 7th Workshop on Algorithms and Models for the Web Graph (WAW) | January 2010

Publication

Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning

Prateek Jain

Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010 | January 2010

Publication

Stability and Incentive Compatibility in a Kernel-Based Combinatorial Auction

Sébastien Lahaie

National Conference on Artificial Intelligence (AAAI) | January 2010