Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Our research
Content type
+
Downloads (456)
+
Events (484)
 
Groups (150)
+
News (2840)
 
People (723)
 
Projects (1158)
+
Publications (12944)
+
Videos (6110)
Labs
Research areas
Algorithms and theory47205 (375)
Communication and collaboration47188 (243)
Computational linguistics47189 (267)
Computational sciences47190 (245)
Computer systems and networking47191 (843)
Computer vision208594 (948)
Data mining and data management208595 (154)
Economics and computation47192 (127)
Education47193 (91)
Gaming47194 (85)
Graphics and multimedia47195 (255)
Hardware and devices47196 (235)
Health and well-being47197 (113)
Human-computer interaction47198 (1007)
Machine learning and intelligence47200 (1022)
Mobile computing208596 (88)
Quantum computing208597 (41)
Search, information retrieval, and knowledge management47199 (749)
Security and privacy47202 (364)
Social media208598 (91)
Social sciences47203 (313)
Software development, programming principles, tools, and languages47204 (679)
Speech recognition, synthesis, and dialog systems208599 (178)
Technology for emerging markets208600 (64)
1–25 of 375
Sort
Show 25 | 50 | 100
1234567Next 
Loris D'Antoni and Margus Veanes

Symbolic tree automata allow transitions to carry predicates over rich alphabet theories, such as linear arithmetic, and therefore extend finite tree automata to operate over infinite alphabets, such as the set of rational numbers. Existing tree automata algorithms rely on the alphabet being finite, and generalizing them to the sym bolic setting is not a trivial task.

In this paper we study the problem of minimizing symbolic tree automata. First, we formally define and prove the basic prope rties...

Publication details
Date: 1 July 2016
Type: Inproceeding
Publisher: IEEE – Institute of Electrical and Electronics Engineers
Joost Renes, Craig Costello, and Lejla Batina

An elliptic curve addition law is said to be complete if it correctly computes the sum of any two points in the elliptic curve group. One of the main reasons for the increased popularity of Edwards curves in the ECG community is that they can allow a complete group law that is also relatively efficient (e.g., when compared to all known addition laws on Edwards curves). Such complete addition formulas can simplify the task of an ECG implementer and, at the same time, can greatly reduce the potential...

Publication details
Date: 1 May 2016
Type: Inproceeding
Publisher: Springer
Nishanth Chandran, Srinivasan Raghuraman, and Dhinakaran Vinayagamurthy
Publication details
Date: 6 March 2016
Type: Inproceeding
Publisher: Springer
Milan Vojnovic and Seyoung Yun

We consider the maximum likelihood parameter estimation problem for a generalized Thurstone choice model, where choices are from comparison sets of two or more items. We provide tight characterizations of the mean square error, as well as necessary and sufficient conditions for correct classification when each item belongs to one of two classes. These results provide insights into how the estimation accuracy depends on the choice of a generalized Thurstone choice model and the structure of comparison...

Publication details
Date: 1 February 2016
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2016-2
Milan Vojnovic and Se-Young Yun

We consider a team selection problem that requires to hire a team of individuals that maximizes a profit function defined as difference of the utility of production and the cost of hiring. We show that for any monotone submodular utility of production and any increasing cost function of the team size with increasing marginal costs, a natural greedy algorithm guarantees a 1 − log(a)/(a − 1)– approximation when a ≤ e and a 1 − a/e(a − 1)–approximation when a ≥ e, where a is the ratio of the utility of...

Publication details
Date: 1 February 2016
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2016-7
Nishanth Chandran, Bhavana Kanukurthi, and Srinivasan Raghuraman
Publication details
Date: 10 January 2016
Type: Inproceeding
Publisher: Springer
Siddhartha Sen, Robert E. Tarjan, and David Hong Kyun Kim
Publication details
Date: 1 January 2016
Type: Article
Koksal A., Gitter A., Beck K., McKenna A., Srivastava S., Bodik R., Wolf-Yadlin A., Fraenkel E., and Fisher J.
Publication details
Date: 1 December 2015
Type: Article
Lim C.Y., Wang H., Woodhouse S., Piterman N., Wernisch L., Fisher J., and Gottgens B.
Publication details
Date: 1 December 2015
Type: Article
Dan Alistarh, Jennifer Iglesias, and Milan Vojnovic

In many applications, the structure of data can be represented by a hyper-graph, where the data items are vertices, and the associations among items are represented by hyper-edges. Equivalently, we are given as input a bipartite graph with two kinds of vertices: items, and associations (which we refer to as topics). We consider the problem of partitioning the set of items into a given number of partitions, such that the maximum number of topics covered by a partition is minimized.

This is a...

Publication details
Date: 1 December 2015
Type: Inproceeding
Woodhouse S.J., Moignard V., Gottgens B., and FIsher J.

New single-cell technologies readily permit gene expression profiling of thousands of cells at single-cell resolution. In this review, we will discuss methods for visualisation and interpretation of single-cell gene expression data, and the computational analysis needed to go from raw data to predictive executable models of gene regulatory network function. We will focus primarily on single-cell real-time quantitative PCR and RNA-sequencing data, but much of what we cover will also be relevant to other...

Publication details
Date: 1 November 2015
Type: Article
Publisher: Nature Publishing Group
Qihang Lin, Zhaosong Lu, and Lin Xiao

We consider the problem of minimizing the sum of two convex functions: one is smooth and given by a gradient oracle, and the other is separable over blocks of coordinates and has a simple known structure over each block. We develop an accelerated randomized proximal coordinate gradient (APCG) method for minimizing such convex composite functions. For strongly convex functions, our method achieves faster linear convergence rates than existing randomized proximal coordinate gradient methods. Without...

Publication details
Date: 1 November 2015
Type: Article
Publisher: SIAM – Society for Industrial and Applied Mathematics
Yoram Bachrach and Ely Porat

We propose an approach for approximating the Jaccard similarity of two streams, for domains where this similarity is known to be high. Our method is based on a reduction from Jaccard similarity to F_2 norm estimation, for which there exists a sketch that is efficient in terms of both size and compute time, which we augment by a sampling technique. Our approach offers an improvement in the fingerprint size that is quadratic in the degree of similarity between the streams. Further, computing our...

Publication details
Date: 1 October 2015
Type: Article
Publisher: Elsevier
Chieh-Han Wu and Yang Song

In modern web-scale applications that collect data from different sources, entity conflation is a challenging task due to various data quality issues. In this paper, we propose a robust and distributed framework to perform conflation on noisy data in the Microsoft Academic Service dataset. Our framework contains two major components. In the offline component, we train a GBDT model to determine whether two papers from different sources should be conflated to the same paper entity. In the online...

Publication details
Date: 1 October 2015
Type: Inproceeding
Publisher: IEEE – Institute of Electrical and Electronics Engineers
Syed Kamran Haider and Dan Alistarh

High memory contention is generally agreed to be a worst-case scenario for concurrent data structures. There has been a significant amount of research effort spent investigating designs which minimize contention, and several programming techniques have been proposed to mitigate its effects. However, there are currently few architectural mechanisms to allow scaling contended data structures at high thread counts.

In this paper, we investigate hardware support for scalable contended data...

Publication details
Date: 1 September 2015
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2015-71
Liwen Xu, Xiaohong Hao, Nicholas D. Lane, Xin Liu, and Thomas Moscibroda

Mobile crowdsourcing is a powerful tool for collecting data of various types. The primary bottleneck in such systems is the high burden placed on the user who must manually collect sensor data or respond in-situ to simple queries (e.g., experience sampling studies). In this work, we present Compressive CrowdSensing (CCS) – a framework that enables compressive sensing techniques to be applied to mobile crowdsourcing scenarios. CCS enables each user to provide significantly reduced amounts of manually...

Publication details
Date: 1 September 2015
Type: Inproceeding
Publisher: ACM – Association for Computing Machinery
Yu Zheng

The advances in location-acquisition and mobile computing techniques have generated massive spatial trajectory data, which represent the mobility of a diversity of moving objects, such as people, vehicles and animals. Many techniques have been proposed for processing, managing and mining trajectory data in the past decade, fostering a broad range of applications. In this article, we conduct a systematic survey on the major research into trajectory data mining, providing a panorama of the field...

Publication details
Date: 1 September 2015
Type: Article
Publisher: ACM – Association for Computing Machinery
Young-Bum Kim, Karl Stratos, Ruhi Sarikaya, and Minwoo Jeong

In natural language understanding (NLU), a user utterance can be labeled differently depending on the domain or application (e.g., weather vs. calendar). Standard domain adaptation techniques are not directly applicable to take advantage of the existing annotations because they assume that the label set is invariant. We propose a solution based on label embeddings induced from canonical correlation analysis (CCA) that reduces the problem to a standard domain adaptation task and allows use of a number of...

Publication details
Date: 29 August 2015
Type: Proceedings
Publisher: ACL – Association for Computational Linguistics
Young-Bum Kim, Karl Stratos, Xiaohu Liu, and Ruhi Sarikaya

In this paper, we introduce the task of selecting compact lexicon from large, noisy gazetteers.
This scenario arises often in practice, in particular spoken language understanding (SLU).
We propose a simple and effective solution based on matrix decomposition techniques:
canonical correlation analysis (CCA) and rank-revealing QR (RRQR) factorization. CCA is first used to derive low-dimensional gazetteer embeddings from domain-specific search logs. Then RRQR is used to find a subset of...

Publication details
Date: 27 August 2015
Type: Proceedings
Publisher: ACL – Association for Computational Linguistics
Yair Zick, Yoram Bachrach, Ian A. Kash, and Peter Key

We consider revenue negotiation problems in iterative settings. In our model, a group of agents has some initial resources, used in order to generate revenue. Agents must agree on some way of dividing resources, but there’s a twist. At every time-step, the revenue shares received at time t are agent resources at time t + 1, and the game is repeated. The key issue here is that the way resources are shared has a dramatic effect on longterm social welfare, so in order to maximize...

Publication details
Date: 1 August 2015
Type: Article
Qizhen Zhang, Haoran Wang, Yang Chen, Tao Qin, Ying Yan, and Thomas Moscibroda

We introduce cost allocation in the cloud, a problem of accounting costs produced by virtual machine workload in the data center to each player in the cloud. Player here can be the size of virtual machine type or the count of virtual machine in the user decided virtual machine packets. We draw this problem by analyzing the cost of real workload in Microsoft Azure. To our best knowledge, the cost allocation in the cloud has never been studied before. Based on the fact that the players in the cloud form...

Publication details
Date: 1 August 2015
Type: Inproceeding
Publisher: SoCC 2015 (Poster)
Loris D’Antoni and Margus Veanes

Symbolic finite automata and transducers augment classic automata and transducers with symbolic alphabets represented as parametric theories. This extension enables to succinctly represent large and potentially infinite alphabets while preserving closure and decidability properties. Extended symbolic finite automata and transducers further extend these objects by allowing transitions to read consecutive input elements in a single step. In this paper we study the properties of these models. In contrast...

Publication details
Date: 1 July 2015
Type: Article
Publisher: Springer
Dan Alistarh, Milan Vojnovic, and Rati Gelashvili

Population protocols, roughly defined as systems consisting of large numbers of simple identical agents, interacting at random and updating their state following simple rules, are an important research topic at the intersection of distributed computing and biology. One of the fundamental tasks that a population protocol may solve is majority: each node starts in one of two states; the goal is for all nodes to reach a correct consensus on which of the two states was initially the majority....

Publication details
Date: 1 July 2015
Type: Inproceeding
Publisher: ACM – Association for Computing Machinery
Woodhouse S., Piterman N., Koksal A., and Fisher J.
Publication details
Date: 1 July 2015
Type: Proceedings
Publisher: Springer
B. Hall, N. Piterman, A. Hajnal, and J Fisher

The establishment of homeostasis among cell growth, differentiation, and apoptosis is of key importance for organogenesis. Stem cells respond to temporally and spatially regulated signals by switching from mitotic proliferation to asymmetric cell division and differentiation. Executable computer models of signaling pathways can accurately reproduce a wide range of biological phenomena by reducing detailed chemical kinetics to a discrete, finite form. Moreover, coordinated cell movements and physical...

Publication details
Date: 1 July 2015
Type: Article
1–25 of 375
Sort
Show 25 | 50 | 100
1234567Next 
> Our research