Our research
Content type
+
Downloads (421)
+
Events (352)
 
Groups (147)
+
News (2466)
 
People (824)
 
Projects (1021)
+
Publications (11430)
+
Videos (4843)
Labs
Research areas
Algorithms and theory47205 (208)
Communication and collaboration47188 (177)
Computational linguistics47189 (143)
Computational sciences47190 (159)
Computer systems and networking47191 (598)
Computer vision208594 (8)
Data mining and data management208595 (3)
Economics and computation47192 (81)
Education47193 (71)
Gaming47194 (63)
Graphics and multimedia47195 (178)
Hardware and devices47196 (173)
Health and well-being47197 (63)
Human-computer interaction47198 (715)
Machine learning and intelligence47200 (597)
Mobile computing208596 (7)
Quantum computing208597 (3)
Search, information retrieval, and knowledge management47199 (562)
Security and privacy47202 (218)
Social media208598 (5)
Social sciences47203 (219)
Software development, programming principles, tools, and languages47204 (495)
Speech recognition, synthesis, and dialog systems208599 (11)
Technology for emerging markets208600 (22)
1–25 of 208
Sort
Show 25 | 50 | 100
1234567Next 
Rakesh Agrawal, Maria Christoforaki, Sreenivas Gollapudi, Anitha Kannan, Krishnaram Kenthapadi, and Adith Swaminathan
We propose a system for mining videos from the web for supplementing the content of electronic textbooks in order to enhance their utility. Textbooks are generally organized into sections such that each section explains very few concepts and every concept is primarily explained in one section. Building upon these principles from the education literature and drawing upon the theory of Formal Concept Analysis, we define the focus of a section in terms of a few indicia, which themselves are combinations of...
Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: Springer
Shipra Agrawal and Nikhil R. Devanur
In this paper, we consider a very general model for exploration-exploitation tradeoff which allows arbitrary concave rewards and convex constraints on the decisions across time, in addition to the customary limitation on the time horizon. This model subsumes the classic multi-armed bandit (MAB) model, and the Bandits with Knapsacks (BwK) model of Badanidiyuru et al.[2013]. We also consider an extension of this model to allow linear contexts, similar to the linear contextual extension of the MAB model. We...
Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: ACM conference on Economics and Computation
Lin Xiao and Tong Zhang
We consider the problem of minimizing the sum of two convex functions: one is the average of a large number of smooth component functions, and the other is a general convex function that admits a simple proximal mapping. We assume the whole objective function is strongly convex. Such problems often arise in machine learning, known as regularized empirical risk minimization. We propose and analyze a new proximal stochastic gradient method, which uses a multi-stage scheme to progressively reduce the variance...
Publication details
Date: 18 March 2014
Type: Technical report
Number: MSR-TR-2014-38
Rakesh Agrawal, Behzad Golshan, and Evimaria Terzi
Given a class of large number of students, each exhibiting a different ability level, how can we form teams of students so that the expected performance of team members improves due to team participation? We take a computational perspective and formally define two versions of such team-formation problem: the MaxTeam and the MaxPartition problems. The first asks for the identification of a single team of students that improves the performance of most of the participating team members. The second asks for a...
Publication details
Date: 1 March 2014
Type: Inproceeding
Publisher: ACM
Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck
We present a versatile and scalable algorithm for computing exact distances on real-world networks with tens of millions of arcs in a few microseconds. Unlike existing approaches, which are specialized, our algorithm works on a wide variety of inputs, including social, communication, sensor, and road networks. Both our indexing effort and query times are comparable to those of specialized systems. We achieve this by providing a unified framework based on the concept of 2-hop labels, building on and...
Publication details
Date: 1 February 2014
Type: Technical report
Publisher: Microsoft Technical Report
Number: MSR-TR-2014-12
Dan Alistarh, Oksana Denysyuk, Luis Rodrigues, and Nir Shavit
We consider the following natural problem: n failure-prone servers, communicating synchronously through message-passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of Omega (log n) communication rounds is known. Second, model the problem as a randomized load-balancing problem, which have elegant...
Publication details
Date: 1 February 2014
Type: Technical report
Number: MSR-TR-2014-17
Dan Alistarh, James Aspnes, Valerie King, and Jared Saia
We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. We describe a new randomized consensus protocol for this model with expected message complexity...
Publication details
Date: 1 February 2014
Type: Technical report
Number: MSR-TR-2014-15
Dan Alistarh, Rati Gelashvili, and Adrian Vladu
We give message-optimal randomized implementations for two fundamental distributed tasks: leader election (test-and-set) and renaming. The setting is an asynchronous message-passing system, where n processors communicate over unreliable channels, controlled by a strong adaptive adversary. We prove that, even though t < n=2 processes may fail by crashing, both tasks can be solved using expected O(n^2) messages|the same asymptotic complexity as a single all-to-all broadcast|and that this message complexity...
Publication details
Date: 1 February 2014
Type: Technical report
Number: MSR-TR-2014-18
Dan Alistarh, Justin Kopinsky, Jerry Li, and Nir Shavit
High-performance concurrent priority queues are essential for applications such as task scheduling and discrete event simulation. Unfortunately even the best performing implementations do not scale past a number of threads in the single digits. This is because of the sequential bottleneck in accessing the elements at the head of the queue in order to perform a DeleteMin operation. In this paper, we present the SprayList, a scalable priority queue with relaxed ordering semantics. Starting from a...
Publication details
Date: 1 February 2014
Type: Technical report
Number: MSR-TR-2014-16
Joppe W. Bos, Craig Costello, Patrick Longa, and Michael Naehrig
We select a set of elliptic curves for cryptography and analyze our selection from a performance and security perspective. This analysis complements recent curve proposals that suggest (twisted) Edwards curves by also considering the Weierstrass model. Working with both Montgomery-friendly and pseudo-Mersenne primes allows us to consider more possibilities which improves the overall efficiency of base field arithmetic. Our Weierstrass curves are backwards compatible with current implementations of prime...
Publication details
Date: 1 February 2014
Type: Technical report
Number: MSR-TR-2014-19
Loris D'Antoni and Margus Veanes
Symbolic Automata extend classical automata by using symbolic alphabets instead of finite ones. Most of the classical automata algorithms rely on the alphabet being finite, and generalizing them to the symbolic setting is not a trivial task. In this paper we study the problem of minimizing symbolic automata. We formally define and prove the basic properties of minimality in the symbolic setting, and lift classical minimization algorithms (Huffman-Moore’s and Hopcroft’s algorithms) to symbolic automata....
Publication details
Date: 1 January 2014
Type: Inproceeding
Publisher: ACM
Joppe W. Bos, Alina Dudeanu, and Dimitar Jetchev
We prove collision bounds for the Pollard rho algorithm to solve the discrete logarithm problem in a general cyclic group G. Unlike the setting studied by Kim et al., we consider additive walks: the setting used in practice to solve the elliptic curve discrete logarithm problem. Our bounds differ from the birthday bound O(sqrt(|G|)) by a factor of sqrt(\log(|\G|)) and are based on mixing time estimates for random walks on finite abelian groups due to Dou and Hildebrand. See also:...
Publication details
Date: 1 January 2014
Type: Article
Publisher: de Gruyter
Rakesh Agrawal, Maria Christoforaki, Sreenivas Gollapudi, Anitha Kannan, Krishnaram Kenthapadi, and Adith Swaminathan
We propose a system for mining videos from the web for supplementing the content of electronic textbooks in order to enhance their utility. Textbooks are generally organized into sections such that each section explains very few concepts and every concept is primarily explained in one section. Building upon these principles from the education literature and drawing upon the theory of Formal Concept Analysis, we define the focus of a section in terms of a few indicia, which themselves are combinations of...
Publication details
Date: 1 January 2014
Type: Technical report
Number: MSR-TR-2014-5
Joppe W. Bos, Craig Costello, and Andrea Miele
Motivated by the advantages of using elliptic curves for discrete logarithm-based public-key cryptography, there is an active research area investigating the potential of using hyperelliptic curves of genus 2. For both types of curves, the best known algorithms to solve the discrete logarithm problem are generic attacks such as Pollard rho, for which it is well-known that the algorithm can be sped up when the target curve comes equipped with an efficiently computable automorphism. In this paper we...
Publication details
Date: 1 January 2014
Type: Inproceeding
Publisher: Springer
Margus Veanes, Nikolaj Bjorner, Lev Nachmanson, and Sergey Bereg
Monadic predicates play a prominent role in many decidable cases, including decision procedures for symbolic automata. We are here interested in discovering whether a formula can be rewritten into a Boolean combination of monadic predicates. Our setting is quantifier-free formulas over a decidable background theory, such as arithmetic and we here develop a semi-decision procedure for extracting a monadic decomposition of a formula when it exists.
Publication details
Date: 1 December 2013
Type: Inproceeding
Publisher: Easychair
Rakesh Agrawal
This paper summarizes the results of our recent investigations into how information propagates, how people assimilate information, and how people form relationships to gain information in Internet-centric social settings. It includes key ideas related to the role of the nature of information items in information diffusion as well as the notion of receptivity on part of the receiver and how it affects information assimilation and opinion formation. It describes a system that incorporates availability,...
Publication details
Date: 1 November 2013
Type: Technical report
Publisher: Microsoft Technical Report
Number: MSR-TR-2013-115
ittai abraham, Omar Alonso, Vasilis Kandylas, Rajesh Patel, Steven Shelford, Aleksandrs Slivkins, and Hai Wu
Gold HITs --- Human Intelligence Tasks with known answers --- are commonly used to measure worker performance and data quality in industrial applications of crowdsourcing. We suggest adaptive exploration as a promising approach for automated, scalable Gold HIT creation. We substantiate this with initial experiments in a stylized model.
Publication details
Date: 22 October 2013
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2013-106
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi
We present study navigator, an algorithmically-generated aid for enhancing the experience of studying from electronic textbooks. The study navigator for a section of the book consists of helpful concept references for understanding this section. Each concept reference is a pair consisting of a concept phrase explained elsewhere and the link to the section in which it has been explained. We propose a novel reader model for textbooks and an algorithm for generating the study navigator based on this model. We...
Publication details
Date: 1 October 2013
Type: Inproceeding
Publisher: ACM
Robert Cochran, Loris D'Antoni, and Benjamin Livshits
A great deal of effort has been spent on both trying to specify software requirements and on ensuring that software actually matches these requirements. A wide range of techniques that includes theorem proving, model checking, type-based analysis, static analysis, runtime monitoring, and the like have been proposed. However, in many areas adoption of these techniques remains spotty. In fact, obtaining a specification or a precise notion of correctness is in many cases quite elusive. For many tasks, even...
Publication details
Date: 26 September 2013
Type: Technical report
Number: MSR-TR-2013-94
Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck
Computing driving directions has motivated many shortest path algorithms based on preprocessing. Given a graph, the preprocessing stage computes a modest amount of auxiliary data, which is then used to speed up on-line queries. The best algorithms have storage overhead comparable to the graph size and answer queries very fast, while examining a small fraction of the graph. In this paper we complement the experimental evidence with the first rigorous proofs of efficiency for some of the algorithms developed...
Publication details
Date: 1 September 2013
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2013-91
Martín Abadi, Dan Boneh, Ilya Mironov, Ananth Raghunathan, and Gil Segev
Motivated by the problem of avoiding duplication in storage systems, Bellare, Keelveedhi, and Ristenpart have recently put forward the notion of Message-Locked Encryption (MLE) schemes which subsumes convergent encryption and its variants. Such schemes do not rely on permanent secret keys, but rather encrypt messages using keys derived from the messages themselves. We strengthen the notions of security proposed by Bellare et al. by considering plaintext distributions that may depend on the public...
Publication details
Date: 1 August 2013
Type: Inproceeding
Publisher: Springer Verlag
Abhimanyu Das, Sreenivas Gollapudi, Rina Panigrahy, and Mahyar Salek
With the explosive growth of social networks, many applications are increasingly harnessing the pulse of online crowds for a variety of tasks such as marketing, advertising, and opinion mining. An important example is the wisdom of crowd effect that has been well studied for such tasks when the crowd is non-interacting. However, these studies don't explicitly address the network effects in social networks. A key difference in this setting is the presence of social influences that arise from these...
Publication details
Date: 1 August 2013
Type: Inproceeding
Publisher: ACM International Conference on Knowledge Discovery and Data Mining
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi
We present study navigator, an algorithmically-generated aid for enhancing the experience of studying from electronic textbooks. The study navigator for a section of the book consists of helpful concept references for understanding this section. Each concept reference is a pair consisting of a concept phrase explained elsewhere and the link to the section in which it has been explained. We propose a novel reader model for textbooks and an algorithm for generating the study navigator based on this model. We...
Publication details
Date: 15 July 2013
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2013-68
Alex Bocharov, Yuri Gurevich, and Krysta M. Svore
We develop the first constructive algorithms for compiling single-qubit unitary gates into circuits over the universal V basis. The V basis is an alternative universal basis to the more commonly studied {H,T} basis. We propose two classical algorithms for quantum circuit compilation: the first algorithm has expected polynomial time (in precision log(1/epsilon)) and offers a depth/precision guarantee that improves upon state-of-the-art methods for compiling into the {H,T} basis by factors ranging from 1.86...
Publication details
Date: 12 July 2013
Type: Article
Publisher: American Physical Society
Number: 012313
Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra
Suppose that party A collects private information about its users, where each user's data is represented as a bit vector. Suppose that party B has a proprietary data mining algorithm that requires estimating the distance between users, such as clustering or nearest neighbors. We ask if it is possible for party A to publish some information about each user so that B can estimate the distance between users without being able to infer any private bit of a user. Our method involves projecting each user's...
Publication details
Date: 1 July 2013
Type: Article
1–25 of 208
Sort
Show 25 | 50 | 100
1234567Next 
> Our research